1/*
2 * Copyright (C) 2008 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#include "reference_table.h"
18
19#include "android-base/stringprintf.h"
20
21#include "base/mutex.h"
22#include "indirect_reference_table.h"
23#include "mirror/array.h"
24#include "mirror/array-inl.h"
25#include "mirror/class.h"
26#include "mirror/class-inl.h"
27#include "mirror/object-inl.h"
28#include "mirror/string-inl.h"
29#include "runtime-inl.h"
30#include "thread.h"
31#include "utils.h"
32
33namespace art {
34
35using android::base::StringAppendF;
36using android::base::StringPrintf;
37
38ReferenceTable::ReferenceTable(const char* name, size_t initial_size, size_t max_size)
39    : name_(name), max_size_(max_size) {
40  CHECK_LE(initial_size, max_size);
41  entries_.reserve(initial_size);
42}
43
44ReferenceTable::~ReferenceTable() {
45}
46
47void ReferenceTable::Add(ObjPtr<mirror::Object> obj) {
48  DCHECK(obj != nullptr);
49  VerifyObject(obj);
50  if (entries_.size() >= max_size_) {
51    LOG(FATAL) << "ReferenceTable '" << name_ << "' "
52               << "overflowed (" << max_size_ << " entries)";
53  }
54  entries_.push_back(GcRoot<mirror::Object>(obj));
55}
56
57void ReferenceTable::Remove(ObjPtr<mirror::Object> obj) {
58  // We iterate backwards on the assumption that references are LIFO.
59  for (int i = entries_.size() - 1; i >= 0; --i) {
60    ObjPtr<mirror::Object> entry = entries_[i].Read();
61    if (entry == obj) {
62      entries_.erase(entries_.begin() + i);
63      return;
64    }
65  }
66}
67
68// If "obj" is an array, return the number of elements in the array.
69// Otherwise, return zero.
70static size_t GetElementCount(ObjPtr<mirror::Object> obj) REQUIRES_SHARED(Locks::mutator_lock_) {
71  // We assume the special cleared value isn't an array in the if statement below.
72  DCHECK(!Runtime::Current()->GetClearedJniWeakGlobal()->IsArrayInstance());
73  if (obj == nullptr || !obj->IsArrayInstance()) {
74    return 0;
75  }
76  return obj->AsArray()->GetLength();
77}
78
79// Log an object with some additional info.
80//
81// Pass in the number of elements in the array (or 0 if this is not an
82// array object), and the number of additional objects that are identical
83// or equivalent to the original.
84static void DumpSummaryLine(std::ostream& os, ObjPtr<mirror::Object> obj, size_t element_count,
85                            int identical, int equiv)
86    REQUIRES_SHARED(Locks::mutator_lock_) {
87  if (obj == nullptr) {
88    os << "    null reference (count=" << equiv << ")\n";
89    return;
90  }
91  if (Runtime::Current()->IsClearedJniWeakGlobal(obj)) {
92    os << "    cleared jweak (count=" << equiv << ")\n";
93    return;
94  }
95
96  std::string className(obj->PrettyTypeOf());
97  if (obj->IsClass()) {
98    // We're summarizing multiple instances, so using the exemplar
99    // Class' type parameter here would be misleading.
100    className = "java.lang.Class";
101  }
102  if (element_count != 0) {
103    StringAppendF(&className, " (%zd elements)", element_count);
104  }
105
106  size_t total = identical + equiv + 1;
107  std::string msg(StringPrintf("%5zd of %s", total, className.c_str()));
108  if (identical + equiv != 0) {
109    StringAppendF(&msg, " (%d unique instances)", equiv + 1);
110  }
111  os << "    " << msg << "\n";
112}
113
114size_t ReferenceTable::Size() const {
115  return entries_.size();
116}
117
118void ReferenceTable::Dump(std::ostream& os) {
119  os << name_ << " reference table dump:\n";
120  Dump(os, entries_);
121}
122
123void ReferenceTable::Dump(std::ostream& os, Table& entries) {
124  // Compare GC roots, first by class, then size, then address.
125  struct GcRootComparator {
126    bool operator()(GcRoot<mirror::Object> root1, GcRoot<mirror::Object> root2) const
127      // TODO: enable analysis when analysis can work with the STL.
128        NO_THREAD_SAFETY_ANALYSIS {
129      Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
130      // These GC roots are already forwarded in ReferenceTable::Dump. We sort by class since there
131      // are no suspend points which can happen during the sorting process. This works since
132      // we are guaranteed that the addresses of obj1, obj2, obj1->GetClass, obj2->GetClass wont
133      // change during the sorting process. The classes are forwarded by ref->GetClass().
134      ObjPtr<mirror::Object> obj1 = root1.Read<kWithoutReadBarrier>();
135      ObjPtr<mirror::Object> obj2 = root2.Read<kWithoutReadBarrier>();
136      DCHECK(obj1 != nullptr);
137      DCHECK(obj2 != nullptr);
138      Runtime* runtime = Runtime::Current();
139      DCHECK(!runtime->IsClearedJniWeakGlobal(obj1));
140      DCHECK(!runtime->IsClearedJniWeakGlobal(obj2));
141      // Sort by class...
142      if (obj1->GetClass() != obj2->GetClass()) {
143        return obj1->GetClass() < obj2->GetClass();
144      }
145      // ...then by size...
146      const size_t size1 = obj1->SizeOf();
147      const size_t size2 = obj2->SizeOf();
148      if (size1 != size2) {
149        return size1 < size2;
150      }
151      // ...and finally by address.
152      return obj1.Ptr() < obj2.Ptr();
153    }
154  };
155
156  if (entries.empty()) {
157    os << "  (empty)\n";
158    return;
159  }
160
161  // Dump the most recent N entries.
162  const size_t kLast = 10;
163  size_t count = entries.size();
164  int first = count - kLast;
165  if (first < 0) {
166    first = 0;
167  }
168  os << "  Last " << (count - first) << " entries (of " << count << "):\n";
169  Runtime* runtime = Runtime::Current();
170  for (int idx = count - 1; idx >= first; --idx) {
171    ObjPtr<mirror::Object> ref = entries[idx].Read();
172    if (ref == nullptr) {
173      continue;
174    }
175    if (runtime->IsClearedJniWeakGlobal(ref)) {
176      os << StringPrintf("    %5d: cleared jweak\n", idx);
177      continue;
178    }
179    if (ref->GetClass() == nullptr) {
180      // should only be possible right after a plain dvmMalloc().
181      size_t size = ref->SizeOf();
182      os << StringPrintf("    %5d: %p (raw) (%zd bytes)\n", idx, ref.Ptr(), size);
183      continue;
184    }
185
186    std::string className(ref->PrettyTypeOf());
187
188    std::string extras;
189    size_t element_count = GetElementCount(ref);
190    if (element_count != 0) {
191      StringAppendF(&extras, " (%zd elements)", element_count);
192    } else if (ref->GetClass()->IsStringClass()) {
193      ObjPtr<mirror::String> s = ref->AsString();
194      std::string utf8(s->ToModifiedUtf8());
195      if (s->GetLength() <= 16) {
196        StringAppendF(&extras, " \"%s\"", utf8.c_str());
197      } else {
198        StringAppendF(&extras, " \"%.16s... (%d chars)", utf8.c_str(), s->GetLength());
199      }
200    } else if (ref->IsReferenceInstance()) {
201      ObjPtr<mirror::Object> referent = ref->AsReference()->GetReferent();
202      if (referent == nullptr) {
203        extras = " (referent is null)";
204      } else {
205        extras = StringPrintf(" (referent is a %s)", referent->PrettyTypeOf().c_str());
206      }
207    }
208    os << StringPrintf("    %5d: ", idx) << ref << " " << className << extras << "\n";
209  }
210
211  // Make a copy of the table and sort it, only adding non null and not cleared elements.
212  Table sorted_entries;
213  for (GcRoot<mirror::Object>& root : entries) {
214    if (!root.IsNull() && !runtime->IsClearedJniWeakGlobal(root.Read())) {
215      sorted_entries.push_back(root);
216    }
217  }
218  if (sorted_entries.empty()) {
219    return;
220  }
221  std::sort(sorted_entries.begin(), sorted_entries.end(), GcRootComparator());
222
223  class SummaryElement {
224   public:
225    GcRoot<mirror::Object> root;
226    size_t equiv;
227    size_t identical;
228
229    SummaryElement() : equiv(0), identical(0) {}
230    SummaryElement(SummaryElement&& ref) {
231      root = ref.root;
232      equiv = ref.equiv;
233      identical = ref.identical;
234    }
235    SummaryElement(const SummaryElement&) = default;
236    SummaryElement& operator=(SummaryElement&&) = default;
237
238    void Reset(GcRoot<mirror::Object>& _root) {
239      root = _root;
240      equiv = 0;
241      identical = 0;
242    }
243  };
244  std::vector<SummaryElement> sorted_summaries;
245  {
246    SummaryElement prev;
247
248    for (GcRoot<mirror::Object>& root : sorted_entries) {
249      ObjPtr<mirror::Object> current = root.Read<kWithoutReadBarrier>();
250
251      if (UNLIKELY(prev.root.IsNull())) {
252        prev.Reset(root);
253        continue;
254      }
255
256      ObjPtr<mirror::Object> prevObj = prev.root.Read<kWithoutReadBarrier>();
257      if (current == prevObj) {
258        // Same reference, added more than once.
259        ++prev.identical;
260      } else if (current->GetClass() == prevObj->GetClass() &&
261          GetElementCount(current) == GetElementCount(prevObj)) {
262        // Same class / element count, different object.
263        ++prev.equiv;
264      } else {
265        sorted_summaries.push_back(prev);
266        prev.Reset(root);
267      }
268      prev.root = root;
269    }
270    sorted_summaries.push_back(prev);
271
272    // Compare summary elements, first by combined count, then by identical (indicating leaks),
273    // then by class (and size and address).
274    struct SummaryElementComparator {
275      GcRootComparator gc_root_cmp;
276
277      bool operator()(SummaryElement& elem1, SummaryElement& elem2) const
278          NO_THREAD_SAFETY_ANALYSIS {
279        Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
280
281        size_t count1 = elem1.equiv + elem1.identical;
282        size_t count2 = elem2.equiv + elem2.identical;
283        if (count1 != count2) {
284          return count1 > count2;
285        }
286
287        if (elem1.identical != elem2.identical) {
288          return elem1.identical > elem2.identical;
289        }
290
291        // Otherwise, compare the GC roots as before.
292        return gc_root_cmp(elem1.root, elem2.root);
293      }
294    };
295    std::sort(sorted_summaries.begin(), sorted_summaries.end(), SummaryElementComparator());
296  }
297
298  // Dump a summary of the whole table.
299  os << "  Summary:\n";
300  for (SummaryElement& elem : sorted_summaries) {
301    ObjPtr<mirror::Object> elemObj = elem.root.Read<kWithoutReadBarrier>();
302    DumpSummaryLine(os, elemObj, GetElementCount(elemObj), elem.identical, elem.equiv);
303  }
304}
305
306void ReferenceTable::VisitRoots(RootVisitor* visitor, const RootInfo& root_info) {
307  BufferedRootVisitor<kDefaultBufferedRootCount> buffered_visitor(visitor, root_info);
308  for (GcRoot<mirror::Object>& root : entries_) {
309    buffered_visitor.VisitRoot(root);
310  }
311}
312
313}  // namespace art
314