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