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 #pragma once
18 
19 #include <ctype.h>
20 #include <inttypes.h>
21 #include <stdint.h>
22 #include <stdlib.h>
23 #include <string.h>
24 #include <sys/types.h>
25 
26 #include <algorithm>  // std::max
27 #include <array>
28 #include <memory>
29 #include <mutex>
30 #include <string>
31 #include <string_view>
32 #include <unordered_map>
33 
34 #include <android-base/stringprintf.h>
35 #include <android-base/thread_annotations.h>
36 #include <android/log.h>
37 #include <log/log_time.h>
38 #include <private/android_filesystem_config.h>
39 #include <utils/FastStrcmp.h>
40 
41 #include "LogUtils.h"
42 
43 #define log_id_for_each(i) \
44     for (log_id_t i = LOG_ID_MIN; (i) < LOG_ID_MAX; (i) = (log_id_t)((i) + 1))
45 
46 class LogStatistics;
47 class UidEntry;
48 class PidEntry;
49 
50 struct LogStatisticsElement {
51     uid_t uid;
52     pid_t pid;
53     pid_t tid;
54     uint32_t tag;
55     log_time realtime;
56     const char* msg;
57     uint16_t msg_len;
58     uint16_t dropped_count;
59     log_id_t log_id;
60     uint16_t total_len;
61 };
62 
63 template <typename TKey, typename TEntry>
64 class LogHashtable {
65     std::unordered_map<TKey, TEntry> map;
66 
bucket_size()67     size_t bucket_size() const {
68         size_t count = 0;
69         for (size_t idx = 0; idx < map.bucket_count(); ++idx) {
70             size_t bucket_size = map.bucket_size(idx);
71             if (bucket_size == 0) bucket_size = 1;
72             count += bucket_size;
73         }
74         float load_factor = map.max_load_factor();
75         if (load_factor < 1.0) return count;
76         return count * load_factor;
77     }
78 
79     static const size_t unordered_map_per_entry_overhead = sizeof(void*);
80     static const size_t unordered_map_bucket_overhead = sizeof(void*);
81 
82   public:
size()83     size_t size() const {
84         return map.size();
85     }
86 
87     // Estimate unordered_map memory usage.
sizeOf()88     size_t sizeOf() const {
89         return sizeof(*this) +
90                (size() * (sizeof(TEntry) + unordered_map_per_entry_overhead)) +
91                (bucket_size() * sizeof(size_t) + unordered_map_bucket_overhead);
92     }
93 
94     typedef typename std::unordered_map<TKey, TEntry>::iterator iterator;
95     typedef
96         typename std::unordered_map<TKey, TEntry>::const_iterator const_iterator;
97 
98     // Returns a sorted array of up to len highest entries sorted by size.  If fewer than len
99     // entries are found, their positions are set to nullptr.
100     template <size_t len>
MaxEntries(uid_t uid,pid_t pid,std::array<const TKey *,len> & out_keys,std::array<const TEntry *,len> & out_entries)101     void MaxEntries(uid_t uid, pid_t pid, std::array<const TKey*, len>& out_keys,
102                     std::array<const TEntry*, len>& out_entries) const {
103         out_keys.fill(nullptr);
104         out_entries.fill(nullptr);
105         for (const auto& [key, entry] : map) {
106             uid_t entry_uid = 0;
107             if constexpr (std::is_same_v<TEntry, UidEntry>) {
108                 entry_uid = key;
109             } else {
110                 entry_uid = entry.uid();
111             }
112             if (uid != AID_ROOT && uid != entry_uid) {
113                 continue;
114             }
115             pid_t entry_pid = 0;
116             if constexpr (std::is_same_v<TEntry, PidEntry>) {
117                 entry_pid = key;
118             } else {
119                 entry_pid = entry.pid();
120             }
121             if (pid && entry_pid && pid != entry_pid) {
122                 continue;
123             }
124 
125             size_t sizes = entry.getSizes();
126             ssize_t index = len - 1;
127             while ((!out_entries[index] || sizes > out_entries[index]->getSizes()) && --index >= 0)
128                 ;
129             if (++index < (ssize_t)len) {
130                 size_t num = len - index - 1;
131                 if (num) {
132                     memmove(&out_keys[index + 1], &out_keys[index], num * sizeof(const TKey*));
133                     memmove(&out_entries[index + 1], &out_entries[index],
134                             num * sizeof(const TEntry*));
135                 }
136                 out_keys[index] = &key;
137                 out_entries[index] = &entry;
138             }
139         }
140     }
141 
Add(const TKey & key,const LogStatisticsElement & element)142     iterator Add(const TKey& key, const LogStatisticsElement& element) {
143         iterator it = map.find(key);
144         if (it == map.end()) {
145             it = map.insert(std::make_pair(key, TEntry(element))).first;
146         } else {
147             it->second.Add(element);
148         }
149         return it;
150     }
151 
Add(const TKey & key)152     iterator Add(const TKey& key) {
153         iterator it = map.find(key);
154         if (it == map.end()) {
155             it = map.insert(std::make_pair(key, TEntry(key))).first;
156         } else {
157             it->second.Add(key);
158         }
159         return it;
160     }
161 
Subtract(const TKey & key,const LogStatisticsElement & element)162     void Subtract(const TKey& key, const LogStatisticsElement& element) {
163         iterator it = map.find(key);
164         if (it != map.end() && it->second.Subtract(element)) {
165             map.erase(it);
166         }
167     }
168 
Drop(const TKey & key,const LogStatisticsElement & element)169     void Drop(const TKey& key, const LogStatisticsElement& element) {
170         iterator it = map.find(key);
171         if (it != map.end()) {
172             it->second.Drop(element);
173         }
174     }
175 
Erase(const TKey & key,const LogStatisticsElement & element)176     void Erase(const TKey& key, const LogStatisticsElement& element) {
177         iterator it = map.find(key);
178         if (it != map.end()) {
179             it->second.Erase(element);
180         }
181     }
182 
begin()183     iterator begin() { return map.begin(); }
begin()184     const_iterator begin() const { return map.begin(); }
end()185     iterator end() { return map.end(); }
end()186     const_iterator end() const { return map.end(); }
187 };
188 
189 class EntryBase {
190   public:
EntryBase()191     EntryBase() : size_(0) {}
EntryBase(const LogStatisticsElement & element)192     explicit EntryBase(const LogStatisticsElement& element) : size_(element.total_len) {}
193 
getSizes()194     size_t getSizes() const { return size_; }
195 
Add(const LogStatisticsElement & element)196     void Add(const LogStatisticsElement& element) { size_ += element.total_len; }
Subtract(const LogStatisticsElement & element)197     bool Subtract(const LogStatisticsElement& element) {
198         size_ -= element.total_len;
199         return size_ == 0;
200     }
Drop(const LogStatisticsElement & element)201     void Drop(const LogStatisticsElement& element) { size_ -= element.msg_len; }
Erase(const LogStatisticsElement & element)202     void Erase(const LogStatisticsElement& element) { size_ -= element.total_len; }
203 
204     static constexpr size_t PRUNED_LEN = 14;
205     static constexpr size_t TOTAL_LEN = 80;
206 
formatLine(const std::string & name,const std::string & size,const std::string & pruned)207     static std::string formatLine(const std::string& name,
208                                   const std::string& size,
209                                   const std::string& pruned) {
210         ssize_t drop_len = std::max(pruned.length() + 1, PRUNED_LEN);
211         ssize_t size_len = std::max(size.length() + 1, TOTAL_LEN - name.length() - drop_len - 1);
212 
213         std::string ret = android::base::StringPrintf(
214             "%s%*s%*s", name.c_str(), (int)size_len, size.c_str(),
215             (int)drop_len, pruned.c_str());
216         // remove any trailing spaces
217         size_t pos = ret.size();
218         size_t len = 0;
219         while (pos && isspace(ret[--pos])) ++len;
220         if (len) ret.erase(pos + 1, len);
221         return ret + "\n";
222     }
223 
224   private:
225     size_t size_;
226 };
227 
228 class EntryBaseDropped : public EntryBase {
229   public:
EntryBaseDropped()230     EntryBaseDropped() : dropped_(0) {}
EntryBaseDropped(const LogStatisticsElement & element)231     explicit EntryBaseDropped(const LogStatisticsElement& element)
232         : EntryBase(element), dropped_(element.dropped_count) {}
233 
dropped_count()234     size_t dropped_count() const { return dropped_; }
235 
Add(const LogStatisticsElement & element)236     void Add(const LogStatisticsElement& element) {
237         dropped_ += element.dropped_count;
238         EntryBase::Add(element);
239     }
Subtract(const LogStatisticsElement & element)240     bool Subtract(const LogStatisticsElement& element) {
241         dropped_ -= element.dropped_count;
242         return EntryBase::Subtract(element) && dropped_ == 0;
243     }
Drop(const LogStatisticsElement & element)244     void Drop(const LogStatisticsElement& element) {
245         dropped_ += 1;
246         EntryBase::Drop(element);
247     }
248 
249   private:
250     size_t dropped_;
251 };
252 
253 class UidEntry : public EntryBaseDropped {
254   public:
UidEntry(const LogStatisticsElement & element)255     explicit UidEntry(const LogStatisticsElement& element)
256         : EntryBaseDropped(element), pid_(element.pid) {}
257 
pid()258     pid_t pid() const { return pid_; }
259 
Add(const LogStatisticsElement & element)260     void Add(const LogStatisticsElement& element) {
261         if (pid_ != element.pid) {
262             pid_ = -1;
263         }
264         EntryBaseDropped::Add(element);
265     }
266 
267     std::string formatHeader(const std::string& name, log_id_t id) const;
268     std::string format(const LogStatistics& stat, log_id_t id, uid_t uid) const;
269 
270   private:
271     pid_t pid_;
272 };
273 
274 namespace android {
275 uid_t pidToUid(pid_t pid);
276 }
277 
278 class PidEntry : public EntryBaseDropped {
279   public:
PidEntry(pid_t pid)280     explicit PidEntry(pid_t pid)
281         : EntryBaseDropped(),
282           uid_(android::pidToUid(pid)),
283           name_(android::pidToName(pid)) {}
PidEntry(const LogStatisticsElement & element)284     explicit PidEntry(const LogStatisticsElement& element)
285         : EntryBaseDropped(element), uid_(element.uid), name_(android::pidToName(element.pid)) {}
PidEntry(const PidEntry & element)286     PidEntry(const PidEntry& element)
287         : EntryBaseDropped(element),
288           uid_(element.uid_),
289           name_(element.name_ ? strdup(element.name_) : nullptr) {}
~PidEntry()290     ~PidEntry() { free(name_); }
291 
uid()292     uid_t uid() const { return uid_; }
name()293     const char* name() const { return name_; }
294 
Add(pid_t new_pid)295     void Add(pid_t new_pid) {
296         if (name_ && !fastcmp<strncmp>(name_, "zygote", 6)) {
297             free(name_);
298             name_ = nullptr;
299         }
300         if (!name_) {
301             name_ = android::pidToName(new_pid);
302         }
303     }
304 
Add(const LogStatisticsElement & element)305     void Add(const LogStatisticsElement& element) {
306         uid_t incoming_uid = element.uid;
307         if (uid() != incoming_uid) {
308             uid_ = incoming_uid;
309             free(name_);
310             name_ = android::pidToName(element.pid);
311         } else {
312             Add(element.pid);
313         }
314         EntryBaseDropped::Add(element);
315     }
316 
317     std::string formatHeader(const std::string& name, log_id_t id) const;
318     std::string format(const LogStatistics& stat, log_id_t id, pid_t pid) const;
319 
320   private:
321     uid_t uid_;
322     char* name_;
323 };
324 
325 class TidEntry : public EntryBaseDropped {
326   public:
TidEntry(pid_t tid,pid_t pid)327     TidEntry(pid_t tid, pid_t pid)
328         : EntryBaseDropped(),
329           pid_(pid),
330           uid_(android::pidToUid(tid)),
331           name_(android::tidToName(tid)) {}
TidEntry(const LogStatisticsElement & element)332     explicit TidEntry(const LogStatisticsElement& element)
333         : EntryBaseDropped(element),
334           pid_(element.pid),
335           uid_(element.uid),
336           name_(android::tidToName(element.tid)) {}
TidEntry(const TidEntry & element)337     TidEntry(const TidEntry& element)
338         : EntryBaseDropped(element),
339           pid_(element.pid_),
340           uid_(element.uid_),
341           name_(element.name_ ? strdup(element.name_) : nullptr) {}
~TidEntry()342     ~TidEntry() { free(name_); }
343 
pid()344     pid_t pid() const { return pid_; }
uid()345     uid_t uid() const { return uid_; }
name()346     const char* name() const { return name_; }
347 
Add(pid_t incomingTid)348     void Add(pid_t incomingTid) {
349         if (name_ && !fastcmp<strncmp>(name_, "zygote", 6)) {
350             free(name_);
351             name_ = nullptr;
352         }
353         if (!name_) {
354             name_ = android::tidToName(incomingTid);
355         }
356     }
357 
Add(const LogStatisticsElement & element)358     void Add(const LogStatisticsElement& element) {
359         uid_t incoming_uid = element.uid;
360         pid_t incoming_pid = element.pid;
361         if (uid() != incoming_uid || pid() != incoming_pid) {
362             uid_ = incoming_uid;
363             pid_ = incoming_pid;
364             free(name_);
365             name_ = android::tidToName(element.tid);
366         } else {
367             Add(element.tid);
368         }
369         EntryBaseDropped::Add(element);
370     }
371 
372     std::string formatHeader(const std::string& name, log_id_t id) const;
373     std::string format(const LogStatistics& stat, log_id_t id, pid_t pid) const;
374 
375   private:
376     pid_t pid_;
377     uid_t uid_;
378     char* name_;
379 };
380 
381 class TagEntry : public EntryBaseDropped {
382   public:
TagEntry(const LogStatisticsElement & element)383     explicit TagEntry(const LogStatisticsElement& element)
384         : EntryBaseDropped(element), tag_(element.tag), pid_(element.pid), uid_(element.uid) {}
385 
key()386     uint32_t key() const { return tag_; }
pid()387     pid_t pid() const { return pid_; }
uid()388     uid_t uid() const { return uid_; }
name()389     const char* name() const { return android::tagToName(tag_); }
390 
Add(const LogStatisticsElement & element)391     void Add(const LogStatisticsElement& element) {
392         if (uid_ != element.uid) {
393             uid_ = -1;
394         }
395         if (pid_ != element.pid) {
396             pid_ = -1;
397         }
398         EntryBaseDropped::Add(element);
399     }
400 
401     std::string formatHeader(const std::string& name, log_id_t id) const;
402     std::string format(const LogStatistics& stat, log_id_t id, uint32_t) const;
403 
404   private:
405     const uint32_t tag_;
406     pid_t pid_;
407     uid_t uid_;
408 };
409 
410 class TagNameEntry : public EntryBase {
411   public:
TagNameEntry(const LogStatisticsElement & element)412     explicit TagNameEntry(const LogStatisticsElement& element)
413         : EntryBase(element), tid_(element.tid), pid_(element.pid), uid_(element.uid) {}
414 
tid()415     pid_t tid() const { return tid_; }
pid()416     pid_t pid() const { return pid_; }
uid()417     uid_t uid() const { return uid_; }
418 
Add(const LogStatisticsElement & element)419     void Add(const LogStatisticsElement& element) {
420         if (uid_ != element.uid) {
421             uid_ = -1;
422         }
423         if (pid_ != element.pid) {
424             pid_ = -1;
425         }
426         if (tid_ != element.tid) {
427             tid_ = -1;
428         }
429         EntryBase::Add(element);
430     }
431 
432     std::string formatHeader(const std::string& name, log_id_t id) const;
433     std::string format(const LogStatistics& stat, log_id_t id, const std::string& key_name) const;
434 
435   private:
436     pid_t tid_;
437     pid_t pid_;
438     uid_t uid_;
439 };
440 
441 class LogStatistics {
442     friend UidEntry;
443     friend PidEntry;
444     friend TidEntry;
445 
446     size_t mSizes[LOG_ID_MAX] GUARDED_BY(lock_);
447     size_t mElements[LOG_ID_MAX] GUARDED_BY(lock_);
448     size_t mDroppedElements[LOG_ID_MAX] GUARDED_BY(lock_);
449     size_t mSizesTotal[LOG_ID_MAX] GUARDED_BY(lock_);
450     size_t mElementsTotal[LOG_ID_MAX] GUARDED_BY(lock_);
451     log_time mOldest[LOG_ID_MAX] GUARDED_BY(lock_);
452     log_time mNewest[LOG_ID_MAX] GUARDED_BY(lock_);
453     log_time mNewestDropped[LOG_ID_MAX] GUARDED_BY(lock_);
454     static std::atomic<size_t> SizesTotal;
455     bool enable;
456 
457     // uid to size list
458     typedef LogHashtable<uid_t, UidEntry> uidTable_t;
459     uidTable_t uidTable[LOG_ID_MAX] GUARDED_BY(lock_);
460 
461     // pid of system to size list
462     typedef LogHashtable<pid_t, PidEntry> pidSystemTable_t;
463     pidSystemTable_t pidSystemTable[LOG_ID_MAX] GUARDED_BY(lock_);
464 
465     // pid to uid list
466     typedef LogHashtable<pid_t, PidEntry> pidTable_t;
467     pidTable_t pidTable GUARDED_BY(lock_);
468 
469     // tid to uid list
470     typedef LogHashtable<pid_t, TidEntry> tidTable_t;
471     tidTable_t tidTable GUARDED_BY(lock_);
472 
473     // tag list
474     typedef LogHashtable<uint32_t, TagEntry> tagTable_t;
475     tagTable_t tagTable GUARDED_BY(lock_);
476 
477     // security tag list
478     tagTable_t securityTagTable GUARDED_BY(lock_);
479 
480     // global tag list
481     typedef LogHashtable<std::string, TagNameEntry> tagNameTable_t;
482     tagNameTable_t tagNameTable;
483 
sizeOf()484     size_t sizeOf() const REQUIRES(lock_) {
485         size_t size = sizeof(*this) + pidTable.sizeOf() + tidTable.sizeOf() +
486                       tagTable.sizeOf() + securityTagTable.sizeOf() +
487                       tagNameTable.sizeOf() +
488                       (pidTable.size() * sizeof(pidTable_t::iterator)) +
489                       (tagTable.size() * sizeof(tagTable_t::iterator));
490         for (const auto& it : pidTable) {
491             const char* name = it.second.name();
492             if (name) size += strlen(name) + 1;
493         }
494         for (const auto& it : tidTable) {
495             const char* name = it.second.name();
496             if (name) size += strlen(name) + 1;
497         }
498         for (const auto& it : tagNameTable) {
499             size += sizeof(std::string);
500             size_t len = it.first.size();
501             // Account for short string optimization: if the string's length is <= 22 bytes for 64
502             // bit or <= 10 bytes for 32 bit, then there is no additional allocation.
503             if ((sizeof(std::string) == 24 && len > 22) ||
504                 (sizeof(std::string) != 24 && len > 10)) {
505                 size += len;
506             }
507         }
508         log_id_for_each(id) {
509             size += uidTable[id].sizeOf();
510             size += uidTable[id].size() * sizeof(uidTable_t::iterator);
511             size += pidSystemTable[id].sizeOf();
512             size += pidSystemTable[id].size() * sizeof(pidSystemTable_t::iterator);
513         }
514         return size;
515     }
516 
517   public:
518     LogStatistics(bool enable_statistics, bool track_total_size,
519                   std::optional<log_time> start_time = {});
520 
521     void AddTotal(log_id_t log_id, uint16_t size) EXCLUDES(lock_);
522 
523     // Add is for adding an element to the log buffer.  It may be a chatty element in the case of
524     // log deduplication.  Add the total size of the element to statistics.
525     void Add(LogStatisticsElement entry) EXCLUDES(lock_);
526     // Subtract is for removing an element from the log buffer.  It may be a chatty element.
527     // Subtract the total size of the element from statistics.
528     void Subtract(LogStatisticsElement entry) EXCLUDES(lock_);
529     // Drop is for converting a normal element into a chatty element. entry->setDropped(1) must
530     // follow this call.  Subtract only msg_len from statistics, since a chatty element will remain.
531     void Drop(LogStatisticsElement entry) EXCLUDES(lock_);
532     // Erase is for coalescing two chatty elements into one.  Erase() is called on the element that
533     // is removed from the log buffer.  Subtract the total size of the element, which is by
534     // definition only the size of the LogBufferElement + list overhead for chatty elements.
535     void Erase(LogStatisticsElement element) EXCLUDES(lock_);
536 
537     void WorstTwoUids(log_id id, size_t threshold, int* worst, size_t* worst_sizes,
538                       size_t* second_worst_sizes) const EXCLUDES(lock_);
539     void WorstTwoTags(size_t threshold, int* worst, size_t* worst_sizes,
540                       size_t* second_worst_sizes) const EXCLUDES(lock_);
541     void WorstTwoSystemPids(log_id id, size_t worst_uid_sizes, int* worst,
542                             size_t* second_worst_sizes) const EXCLUDES(lock_);
543 
544     bool ShouldPrune(log_id id, unsigned long max_size, unsigned long* prune_rows) const
545             EXCLUDES(lock_);
546 
547     // Return the consumed size of the given buffer.
Sizes(log_id_t id)548     size_t Sizes(log_id_t id) const EXCLUDES(lock_) {
549         auto lock = std::lock_guard{lock_};
550         if (overhead_[id]) {
551             return *overhead_[id];
552         }
553         return mSizes[id];
554     }
555 
556     // Return the uncompressed size of the contents of the given buffer.
SizeReadable(log_id_t id)557     size_t SizeReadable(log_id_t id) const EXCLUDES(lock_) {
558         auto lock = std::lock_guard{lock_};
559         return mSizes[id];
560     }
561 
562     // TODO: Get rid of this entirely.
sizesTotal()563     static size_t sizesTotal() {
564         return SizesTotal;
565     }
566 
567     std::string ReportInteresting() const EXCLUDES(lock_);
568     std::string Format(uid_t uid, pid_t pid, unsigned int logMask) const EXCLUDES(lock_);
569 
570     const char* PidToName(pid_t pid) const EXCLUDES(lock_);
571     uid_t PidToUid(pid_t pid) EXCLUDES(lock_);
572     const char* UidToName(uid_t uid) const EXCLUDES(lock_);
573 
set_overhead(log_id_t id,size_t size)574     void set_overhead(log_id_t id, size_t size) {
575         auto lock = std::lock_guard{lock_};
576         overhead_[id] = size;
577     }
578 
579   private:
580     template <typename TKey, typename TEntry>
581     void WorstTwoWithThreshold(const LogHashtable<TKey, TEntry>& table, size_t threshold,
582                                int* worst, size_t* worst_sizes, size_t* second_worst_sizes) const;
583     template <typename TKey, typename TEntry>
584     std::string FormatTable(const LogHashtable<TKey, TEntry>& table, uid_t uid, pid_t pid,
585                             const std::string& name = std::string(""),
586                             log_id_t id = LOG_ID_MAX) const REQUIRES(lock_);
587     void FormatTmp(const char* nameTmp, uid_t uid, std::string& name, std::string& size,
588                    size_t nameLen) const REQUIRES(lock_);
589     const char* UidToNameLocked(uid_t uid) const REQUIRES(lock_);
590 
591     mutable std::mutex lock_;
592     bool track_total_size_;
593 
594     std::optional<size_t> overhead_[LOG_ID_MAX] GUARDED_BY(lock_);
595 };
596