1// Copyright 2011 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#ifndef V8_LIVEOBJECTLIST_H_
29#define V8_LIVEOBJECTLIST_H_
30
31#include "v8.h"
32
33#include "checks.h"
34#include "heap.h"
35#include "objects.h"
36#include "globals.h"
37
38namespace v8 {
39namespace internal {
40
41#ifdef LIVE_OBJECT_LIST
42
43#ifdef DEBUG
44// The following symbol when defined enables thorough verification of lol data.
45// FLAG_verify_lol will also need to set to true to enable the verification.
46#define VERIFY_LOL
47#endif
48
49
50typedef int LiveObjectType;
51class LolFilter;
52class LiveObjectSummary;
53class DumpWriter;
54class SummaryWriter;
55
56
57// The LiveObjectList is both a mechanism for tracking a live capture of
58// objects in the JS heap, as well as is the data structure which represents
59// each of those captures.  Unlike a snapshot, the lol is live.  For example,
60// if an object in a captured lol dies and is collected by the GC, the lol
61// will reflect that the object is no longer available.  The term
62// LiveObjectList (and lol) is used to describe both the mechanism and the
63// data structure depending on context of use.
64//
65// In captured lols, objects are tracked using their address and an object id.
66// The object id is unique.  Once assigned to an object, the object id can never
67// be assigned to another object.  That is unless all captured lols are deleted
68// which allows the user to start over with a fresh set of lols and object ids.
69// The uniqueness of the object ids allows the user to track specific objects
70// and inspect its longevity while debugging JS code in execution.
71//
72// The lol comes with utility functions to capture, dump, summarize, and diff
73// captured lols amongst other functionality.  These functionality are
74// accessible via the v8 debugger interface.
75class LiveObjectList {
76 public:
77  inline static void GCEpilogue();
78  inline static void GCPrologue();
79  inline static void IterateElements(ObjectVisitor* v);
80  inline static void ProcessNonLive(HeapObject* obj);
81  inline static void UpdateReferencesForScavengeGC();
82
83  // Note: LOLs can be listed by calling Dump(0, <lol id>), and 2 LOLs can be
84  // compared/diff'ed using Dump(<lol id1>, <lol id2>, ...).  This will yield
85  // a verbose dump of all the objects in the resultant lists.
86  //   Similarly, a summarized result of a LOL listing or a diff can be
87  // attained using the Summarize(0, <lol id>) and Summarize(<lol id1,
88  // <lol id2>, ...) respectively.
89
90  static MaybeObject* Capture();
91  static bool Delete(int id);
92  static MaybeObject* Dump(int id1,
93                           int id2,
94                           int start_idx,
95                           int dump_limit,
96                           Handle<JSObject> filter_obj);
97  static MaybeObject* Info(int start_idx, int dump_limit);
98  static MaybeObject* Summarize(int id1, int id2, Handle<JSObject> filter_obj);
99
100  static void Reset();
101  static Object* GetObj(int obj_id);
102  static int GetObjId(Object* obj);
103  static Object* GetObjId(Handle<String> address);
104  static MaybeObject* GetObjRetainers(int obj_id,
105                                      Handle<JSObject> instance_filter,
106                                      bool verbose,
107                                      int start,
108                                      int count,
109                                      Handle<JSObject> filter_obj);
110
111  static Object* GetPath(int obj_id1,
112                         int obj_id2,
113                         Handle<JSObject> instance_filter);
114  static Object* PrintObj(int obj_id);
115
116 private:
117  struct Element {
118    int id_;
119    HeapObject* obj_;
120  };
121
122  explicit LiveObjectList(LiveObjectList* prev, int capacity);
123  ~LiveObjectList();
124
125  static void GCEpiloguePrivate();
126  static void IterateElementsPrivate(ObjectVisitor* v);
127
128  static void DoProcessNonLive(HeapObject* obj);
129
130  static int CompareElement(const Element* a, const Element* b);
131
132  static Object* GetPathPrivate(HeapObject* obj1, HeapObject* obj2);
133
134  static int GetRetainers(Handle<HeapObject> target,
135                          Handle<JSObject> instance_filter,
136                          Handle<FixedArray> retainers_arr,
137                          int start,
138                          int dump_limit,
139                          int* total_count,
140                          LolFilter* filter,
141                          LiveObjectSummary* summary,
142                          JSFunction* arguments_function,
143                          Handle<Object> error);
144
145  static MaybeObject* DumpPrivate(DumpWriter* writer,
146                                  int start,
147                                  int dump_limit,
148                                  LolFilter* filter);
149  static MaybeObject* SummarizePrivate(SummaryWriter* writer,
150                                       LolFilter* filter,
151                                       bool is_tracking_roots);
152
153  static bool NeedLOLProcessing() { return (last() != NULL); }
154  static void NullifyNonLivePointer(HeapObject** p) {
155    // Mask out the low bit that marks this as a heap object.  We'll use this
156    // cleared bit as an indicator that this pointer needs to be collected.
157    //
158    // Meanwhile, we still preserve its approximate value so that we don't
159    // have to resort the elements list all the time.
160    //
161    // Note: Doing so also makes this HeapObject* look like an SMI.  Hence,
162    // GC pointer updater will ignore it when it gets scanned.
163    *p = reinterpret_cast<HeapObject*>((*p)->address());
164  }
165
166  LiveObjectList* prev() { return prev_; }
167  LiveObjectList* next() { return next_; }
168  int id() { return id_; }
169
170  static int list_count() { return list_count_; }
171  static LiveObjectList* last() { return last_; }
172
173  inline static LiveObjectList* FindLolForId(int id, LiveObjectList* start_lol);
174  int TotalObjCount() { return GetTotalObjCountAndSize(NULL); }
175  int GetTotalObjCountAndSize(int* size_p);
176
177  bool Add(HeapObject* obj);
178  Element* Find(HeapObject* obj);
179  static void NullifyMostRecent(HeapObject* obj);
180  void Sort();
181  static void SortAll();
182
183  static void PurgeDuplicates();  // Only to be called by GCEpilogue.
184
185#ifdef VERIFY_LOL
186  static void Verify(bool match_heap_exactly = false);
187  static void VerifyNotInFromSpace();
188#endif
189
190  // Iterates the elements in every lol and returns the one that matches the
191  // specified key.  If no matching element is found, then it returns NULL.
192  template <typename T>
193  inline static LiveObjectList::Element*
194      FindElementFor(T (*GetValue)(LiveObjectList::Element*), T key);
195
196  inline static int GetElementId(Element* element);
197  inline static HeapObject* GetElementObj(Element* element);
198
199  // Instance fields.
200  LiveObjectList* prev_;
201  LiveObjectList* next_;
202  int id_;
203  int capacity_;
204  int obj_count_;
205  Element* elements_;
206
207  // Statics for managing all the lists.
208  static uint32_t next_element_id_;
209  static int list_count_;
210  static int last_id_;
211  static LiveObjectList* first_;
212  static LiveObjectList* last_;
213
214  friend class LolIterator;
215  friend class LolForwardIterator;
216  friend class LolDumpWriter;
217  friend class RetainersDumpWriter;
218  friend class RetainersSummaryWriter;
219  friend class UpdateLiveObjectListVisitor;
220};
221
222
223// Helper class for updating the LiveObjectList HeapObject pointers.
224class UpdateLiveObjectListVisitor: public ObjectVisitor {
225 public:
226  void VisitPointer(Object** p) { UpdatePointer(p); }
227
228  void VisitPointers(Object** start, Object** end) {
229    // Copy all HeapObject pointers in [start, end).
230    for (Object** p = start; p < end; p++) UpdatePointer(p);
231  }
232
233 private:
234  // Based on Heap::ScavengeObject() but only does forwarding of pointers
235  // to live new space objects, and not actually keep them alive.
236  void UpdatePointer(Object** p) {
237    Object* object = *p;
238    if (!HEAP->InNewSpace(object)) return;
239
240    HeapObject* heap_obj = HeapObject::cast(object);
241    ASSERT(HEAP->InFromSpace(heap_obj));
242
243    // We use the first word (where the map pointer usually is) of a heap
244    // object to record the forwarding pointer.  A forwarding pointer can
245    // point to an old space, the code space, or the to space of the new
246    // generation.
247    MapWord first_word = heap_obj->map_word();
248
249    // If the first word is a forwarding address, the object has already been
250    // copied.
251    if (first_word.IsForwardingAddress()) {
252      *p = first_word.ToForwardingAddress();
253      return;
254
255    // Else, it's a dead object.
256    } else {
257      LiveObjectList::NullifyNonLivePointer(reinterpret_cast<HeapObject**>(p));
258    }
259  }
260};
261
262
263#else  // !LIVE_OBJECT_LIST
264
265
266class LiveObjectList {
267 public:
268  inline static void GCEpilogue() {}
269  inline static void GCPrologue() {}
270  inline static void IterateElements(ObjectVisitor* v) {}
271  inline static void ProcessNonLive(HeapObject* obj) {}
272  inline static void UpdateReferencesForScavengeGC() {}
273
274  inline static MaybeObject* Capture() { return HEAP->undefined_value(); }
275  inline static bool Delete(int id) { return false; }
276  inline static MaybeObject* Dump(int id1,
277                                  int id2,
278                                  int start_idx,
279                                  int dump_limit,
280                                  Handle<JSObject> filter_obj) {
281    return HEAP->undefined_value();
282  }
283  inline static MaybeObject* Info(int start_idx, int dump_limit) {
284    return HEAP->undefined_value();
285  }
286  inline static MaybeObject* Summarize(int id1,
287                                       int id2,
288                                       Handle<JSObject> filter_obj) {
289    return HEAP->undefined_value();
290  }
291
292  inline static void Reset() {}
293  inline static Object* GetObj(int obj_id) { return HEAP->undefined_value(); }
294  inline static Object* GetObjId(Handle<String> address) {
295    return HEAP->undefined_value();
296  }
297  inline static MaybeObject* GetObjRetainers(int obj_id,
298                                             Handle<JSObject> instance_filter,
299                                             bool verbose,
300                                             int start,
301                                             int count,
302                                             Handle<JSObject> filter_obj) {
303    return HEAP->undefined_value();
304  }
305
306  inline static Object* GetPath(int obj_id1,
307                                int obj_id2,
308                                Handle<JSObject> instance_filter) {
309    return HEAP->undefined_value();
310  }
311  inline static Object* PrintObj(int obj_id) { return HEAP->undefined_value(); }
312};
313
314
315#endif  // LIVE_OBJECT_LIST
316
317} }  // namespace v8::internal
318
319#endif  // V8_LIVEOBJECTLIST_H_
320