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 <memory> 29 #include <string> 30 #include <string_view> 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 45 class LogStatistics; 46 47 template <typename TKey, typename TEntry> 48 class 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 204 namespace EntryBaseConstants { 205 static constexpr size_t pruned_len = 14; 206 static constexpr size_t total_len = 80; 207 } 208 209 struct 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 251 struct 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 278 struct 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 309 struct 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 375 struct 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 457 struct 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 496 struct TagNameKey { 497 std::string* alloc; 498 std::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::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::string_view(alloc->c_str(), alloc->size()); 515 return; 516 } 517 const char* msg = element->getMsg(); 518 if (!msg) { 519 name = std::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::string_view("<NULL>", strlen("<NULL>")); 527 return; 528 } 529 alloc = new std::string(msg, len); 530 if (!alloc) return; 531 name = std::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::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 574 template <> 575 struct 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::string_view>()(std::string_view(__t)); 580 } 581 }; 582 583 struct TagNameEntry : public EntryBase { 584 pid_t tid; 585 pid_t pid; 586 uid_t uid; 587 TagNameKey name; 588 589 explicit TagNameEntry(const LogBufferElement* element) 590 : EntryBase(element), 591 tid(element->getTid()), 592 pid(element->getPid()), 593 uid(element->getUid()), 594 name(element) { 595 } 596 597 const TagNameKey& getKey() const { 598 return name; 599 } 600 const pid_t& getTid() const { 601 return tid; 602 } 603 const pid_t& getPid() const { 604 return pid; 605 } 606 const uid_t& getUid() const { 607 return uid; 608 } 609 const char* getName() const { 610 return name.data(); 611 } 612 size_t getNameAllocLength() const { 613 return name.getAllocLength(); 614 } 615 616 inline void add(const LogBufferElement* element) { 617 if (uid != element->getUid()) { 618 uid = -1; 619 } 620 if (pid != element->getPid()) { 621 pid = -1; 622 } 623 if (tid != element->getTid()) { 624 tid = -1; 625 } 626 EntryBase::add(element); 627 } 628 629 std::string formatHeader(const std::string& name, log_id_t id) const; 630 std::string format(const LogStatistics& stat, log_id_t id) const; 631 }; 632 633 template <typename TEntry> 634 class LogFindWorst { 635 std::unique_ptr<const TEntry* []> sorted; 636 637 public: 638 explicit LogFindWorst(std::unique_ptr<const TEntry* []>&& sorted) 639 : sorted(std::move(sorted)) { 640 } 641 642 void findWorst(int& worst, size_t& worst_sizes, size_t& second_worst_sizes, 643 size_t threshold) { 644 if (sorted.get() && sorted[0] && sorted[1]) { 645 worst_sizes = sorted[0]->getSizes(); 646 if ((worst_sizes > threshold) 647 // Allow time horizon to extend roughly tenfold, assume 648 // average entry length is 100 characters. 649 && (worst_sizes > (10 * sorted[0]->getDropped()))) { 650 worst = sorted[0]->getKey(); 651 second_worst_sizes = sorted[1]->getSizes(); 652 if (second_worst_sizes < threshold) { 653 second_worst_sizes = threshold; 654 } 655 } 656 } 657 } 658 659 void findWorst(int& worst, size_t worst_sizes, size_t& second_worst_sizes) { 660 if (sorted.get() && sorted[0] && sorted[1]) { 661 worst = sorted[0]->getKey(); 662 second_worst_sizes = 663 worst_sizes - sorted[0]->getSizes() + sorted[1]->getSizes(); 664 } 665 } 666 }; 667 668 // Log Statistics 669 class LogStatistics { 670 friend UidEntry; 671 672 size_t mSizes[LOG_ID_MAX]; 673 size_t mElements[LOG_ID_MAX]; 674 size_t mDroppedElements[LOG_ID_MAX]; 675 size_t mSizesTotal[LOG_ID_MAX]; 676 size_t mElementsTotal[LOG_ID_MAX]; 677 log_time mOldest[LOG_ID_MAX]; 678 log_time mNewest[LOG_ID_MAX]; 679 log_time mNewestDropped[LOG_ID_MAX]; 680 static size_t SizesTotal; 681 bool enable; 682 683 // uid to size list 684 typedef LogHashtable<uid_t, UidEntry> uidTable_t; 685 uidTable_t uidTable[LOG_ID_MAX]; 686 687 // pid of system to size list 688 typedef LogHashtable<pid_t, PidEntry> pidSystemTable_t; 689 pidSystemTable_t pidSystemTable[LOG_ID_MAX]; 690 691 // pid to uid list 692 typedef LogHashtable<pid_t, PidEntry> pidTable_t; 693 pidTable_t pidTable; 694 695 // tid to uid list 696 typedef LogHashtable<pid_t, TidEntry> tidTable_t; 697 tidTable_t tidTable; 698 699 // tag list 700 typedef LogHashtable<uint32_t, TagEntry> tagTable_t; 701 tagTable_t tagTable; 702 703 // security tag list 704 tagTable_t securityTagTable; 705 706 // global tag list 707 typedef LogHashtable<TagNameKey, TagNameEntry> tagNameTable_t; 708 tagNameTable_t tagNameTable; 709 710 size_t sizeOf() const { 711 size_t size = sizeof(*this) + pidTable.sizeOf() + tidTable.sizeOf() + 712 tagTable.sizeOf() + securityTagTable.sizeOf() + 713 tagNameTable.sizeOf() + 714 (pidTable.size() * sizeof(pidTable_t::iterator)) + 715 (tagTable.size() * sizeof(tagTable_t::iterator)); 716 for (auto it : pidTable) { 717 const char* name = it.second.getName(); 718 if (name) size += strlen(name) + 1; 719 } 720 for (auto it : tidTable) { 721 const char* name = it.second.getName(); 722 if (name) size += strlen(name) + 1; 723 } 724 for (auto it : tagNameTable) size += it.second.getNameAllocLength(); 725 log_id_for_each(id) { 726 size += uidTable[id].sizeOf(); 727 size += uidTable[id].size() * sizeof(uidTable_t::iterator); 728 size += pidSystemTable[id].sizeOf(); 729 size += 730 pidSystemTable[id].size() * sizeof(pidSystemTable_t::iterator); 731 } 732 return size; 733 } 734 735 public: 736 LogStatistics(); 737 738 void enableStatistics() { 739 enable = true; 740 } 741 742 void addTotal(LogBufferElement* entry); 743 void add(LogBufferElement* entry); 744 void subtract(LogBufferElement* entry); 745 // entry->setDropped(1) must follow this call 746 void drop(LogBufferElement* entry); 747 // Correct for coalescing two entries referencing dropped content 748 void erase(LogBufferElement* element) { 749 log_id_t log_id = element->getLogId(); 750 --mElements[log_id]; 751 --mDroppedElements[log_id]; 752 } 753 754 LogFindWorst<UidEntry> sort(uid_t uid, pid_t pid, size_t len, log_id id) { 755 return LogFindWorst<UidEntry>(uidTable[id].sort(uid, pid, len)); 756 } 757 LogFindWorst<PidEntry> sortPids(uid_t uid, pid_t pid, size_t len, 758 log_id id) { 759 return LogFindWorst<PidEntry>(pidSystemTable[id].sort(uid, pid, len)); 760 } 761 LogFindWorst<TagEntry> sortTags(uid_t uid, pid_t pid, size_t len, log_id) { 762 return LogFindWorst<TagEntry>(tagTable.sort(uid, pid, len)); 763 } 764 765 // fast track current value by id only 766 size_t sizes(log_id_t id) const { 767 return mSizes[id]; 768 } 769 size_t elements(log_id_t id) const { 770 return mElements[id]; 771 } 772 size_t realElements(log_id_t id) const { 773 return mElements[id] - mDroppedElements[id]; 774 } 775 size_t sizesTotal(log_id_t id) const { 776 return mSizesTotal[id]; 777 } 778 size_t elementsTotal(log_id_t id) const { 779 return mElementsTotal[id]; 780 } 781 static size_t sizesTotal() { 782 return SizesTotal; 783 } 784 785 std::string format(uid_t uid, pid_t pid, unsigned int logMask) const; 786 787 // helper (must be locked directly or implicitly by mLogElementsLock) 788 const char* pidToName(pid_t pid) const; 789 uid_t pidToUid(pid_t pid); 790 pid_t tidToPid(pid_t tid); 791 const char* uidToName(uid_t uid) const; 792 }; 793 794 #endif // _LOGD_LOG_STATISTICS_H__ 795
