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#ifdef LIVE_OBJECT_LIST
29
30#include <ctype.h>
31#include <stdlib.h>
32
33#include "v8.h"
34
35#include "checks.h"
36#include "global-handles.h"
37#include "heap.h"
38#include "inspector.h"
39#include "isolate.h"
40#include "list-inl.h"
41#include "liveobjectlist-inl.h"
42#include "string-stream.h"
43#include "v8utils.h"
44#include "v8conversions.h"
45
46namespace v8 {
47namespace internal {
48
49
50typedef int (*RawComparer)(const void*, const void*);
51
52
53#ifdef CHECK_ALL_OBJECT_TYPES
54
55#define DEBUG_LIVE_OBJECT_TYPES(v) \
56  v(Smi, "unexpected: Smi") \
57  \
58  v(CodeCache, "unexpected: CodeCache") \
59  v(BreakPointInfo, "unexpected: BreakPointInfo") \
60  v(DebugInfo, "unexpected: DebugInfo") \
61  v(TypeSwitchInfo, "unexpected: TypeSwitchInfo") \
62  v(SignatureInfo, "unexpected: SignatureInfo") \
63  v(Script, "unexpected: Script") \
64  v(ObjectTemplateInfo, "unexpected: ObjectTemplateInfo") \
65  v(FunctionTemplateInfo, "unexpected: FunctionTemplateInfo") \
66  v(CallHandlerInfo, "unexpected: CallHandlerInfo") \
67  v(InterceptorInfo, "unexpected: InterceptorInfo") \
68  v(AccessCheckInfo, "unexpected: AccessCheckInfo") \
69  v(AccessorInfo, "unexpected: AccessorInfo") \
70  v(ExternalTwoByteString, "unexpected: ExternalTwoByteString") \
71  v(ExternalAsciiString, "unexpected: ExternalAsciiString") \
72  v(ExternalString, "unexpected: ExternalString") \
73  v(SeqTwoByteString, "unexpected: SeqTwoByteString") \
74  v(SeqAsciiString, "unexpected: SeqAsciiString") \
75  v(SeqString, "unexpected: SeqString") \
76  v(JSFunctionResultCache, "unexpected: JSFunctionResultCache") \
77  v(GlobalContext, "unexpected: GlobalContext") \
78  v(MapCache, "unexpected: MapCache") \
79  v(CodeCacheHashTable, "unexpected: CodeCacheHashTable") \
80  v(CompilationCacheTable, "unexpected: CompilationCacheTable") \
81  v(SymbolTable, "unexpected: SymbolTable") \
82  v(Dictionary, "unexpected: Dictionary") \
83  v(HashTable, "unexpected: HashTable") \
84  v(DescriptorArray, "unexpected: DescriptorArray") \
85  v(ExternalFloatArray, "unexpected: ExternalFloatArray") \
86  v(ExternalUnsignedIntArray, "unexpected: ExternalUnsignedIntArray") \
87  v(ExternalIntArray, "unexpected: ExternalIntArray") \
88  v(ExternalUnsignedShortArray, "unexpected: ExternalUnsignedShortArray") \
89  v(ExternalShortArray, "unexpected: ExternalShortArray") \
90  v(ExternalUnsignedByteArray, "unexpected: ExternalUnsignedByteArray") \
91  v(ExternalByteArray, "unexpected: ExternalByteArray") \
92  v(JSValue, "unexpected: JSValue")
93
94#else
95#define DEBUG_LIVE_OBJECT_TYPES(v)
96#endif
97
98
99#define FOR_EACH_LIVE_OBJECT_TYPE(v) \
100  DEBUG_LIVE_OBJECT_TYPES(v) \
101  \
102  v(JSArray, "JSArray") \
103  v(JSRegExp, "JSRegExp") \
104  v(JSFunction, "JSFunction") \
105  v(JSGlobalObject, "JSGlobal") \
106  v(JSBuiltinsObject, "JSBuiltins") \
107  v(GlobalObject, "Global") \
108  v(JSGlobalProxy, "JSGlobalProxy") \
109  v(JSObject, "JSObject") \
110  \
111  v(Context, "meta: Context") \
112  v(ByteArray, "meta: ByteArray") \
113  v(ExternalPixelArray, "meta: PixelArray") \
114  v(ExternalArray, "meta: ExternalArray") \
115  v(FixedArray, "meta: FixedArray") \
116  v(String, "String") \
117  v(HeapNumber, "HeapNumber") \
118  \
119  v(Code, "meta: Code") \
120  v(Map, "meta: Map") \
121  v(Oddball, "Oddball") \
122  v(Foreign, "meta: Foreign") \
123  v(SharedFunctionInfo, "meta: SharedFunctionInfo") \
124  v(Struct, "meta: Struct") \
125  \
126  v(HeapObject, "HeapObject")
127
128
129enum /* LiveObjectType */ {
130#define DECLARE_OBJECT_TYPE_ENUM(type, name) kType##type,
131  FOR_EACH_LIVE_OBJECT_TYPE(DECLARE_OBJECT_TYPE_ENUM)
132  kInvalidLiveObjType,
133  kNumberOfTypes
134#undef DECLARE_OBJECT_TYPE_ENUM
135};
136
137
138LiveObjectType GetObjectType(HeapObject* heap_obj) {
139  // TODO(mlam): investigate usint Map::instance_type() instead.
140#define CHECK_FOR_OBJECT_TYPE(type, name) \
141  if (heap_obj->Is##type()) return kType##type;
142  FOR_EACH_LIVE_OBJECT_TYPE(CHECK_FOR_OBJECT_TYPE)
143#undef CHECK_FOR_OBJECT_TYPE
144
145  UNREACHABLE();
146  return kInvalidLiveObjType;
147}
148
149
150inline const char* GetObjectTypeDesc(LiveObjectType type) {
151  static const char* const name[kNumberOfTypes] = {
152  #define DEFINE_OBJECT_TYPE_NAME(type, name) name,
153    FOR_EACH_LIVE_OBJECT_TYPE(DEFINE_OBJECT_TYPE_NAME)
154    "invalid"
155  #undef DEFINE_OBJECT_TYPE_NAME
156  };
157  ASSERT(type < kNumberOfTypes);
158  return name[type];
159}
160
161
162const char* GetObjectTypeDesc(HeapObject* heap_obj) {
163  LiveObjectType type = GetObjectType(heap_obj);
164  return GetObjectTypeDesc(type);
165}
166
167
168bool IsOfType(LiveObjectType type, HeapObject* obj) {
169  // Note: there are types that are more general (e.g. JSObject) that would
170  // have passed the Is##type_() test for more specialized types (e.g.
171  // JSFunction).  If we find a more specialized match but we're looking for
172  // the general type, then we should reject the ones that matches the
173  // specialized type.
174#define CHECK_OBJECT_TYPE(type_, name) \
175  if (obj->Is##type_()) return (type == kType##type_);
176
177  FOR_EACH_LIVE_OBJECT_TYPE(CHECK_OBJECT_TYPE)
178#undef CHECK_OBJECT_TYPE
179
180  return false;
181}
182
183
184const AllocationSpace kInvalidSpace = static_cast<AllocationSpace>(-1);
185
186static AllocationSpace FindSpaceFor(String* space_str) {
187  SmartArrayPointer<char> s =
188      space_str->ToCString(DISALLOW_NULLS, ROBUST_STRING_TRAVERSAL);
189
190  const char* key_str = *s;
191  switch (key_str[0]) {
192    case 'c':
193      if (strcmp(key_str, "cell") == 0) return CELL_SPACE;
194      if (strcmp(key_str, "code") == 0) return CODE_SPACE;
195      break;
196    case 'l':
197      if (strcmp(key_str, "lo") == 0) return LO_SPACE;
198      break;
199    case 'm':
200      if (strcmp(key_str, "map") == 0) return MAP_SPACE;
201      break;
202    case 'n':
203      if (strcmp(key_str, "new") == 0) return NEW_SPACE;
204      break;
205    case 'o':
206      if (strcmp(key_str, "old-pointer") == 0) return OLD_POINTER_SPACE;
207      if (strcmp(key_str, "old-data") == 0) return OLD_DATA_SPACE;
208      break;
209  }
210  return kInvalidSpace;
211}
212
213
214static bool InSpace(AllocationSpace space, HeapObject* heap_obj) {
215  Heap* heap = ISOLATE->heap();
216  if (space != LO_SPACE) {
217    return heap->InSpace(heap_obj, space);
218  }
219
220  // This is an optimization to speed up the check for an object in the LO
221  // space by exclusion because we know that all object pointers passed in
222  // here are guaranteed to be in the heap.  Hence, it is safe to infer
223  // using an exclusion test.
224  // Note: calling Heap::InSpace(heap_obj, LO_SPACE) is too slow for our
225  // filters.
226  int first_space = static_cast<int>(FIRST_SPACE);
227  int last_space = static_cast<int>(LO_SPACE);
228  for (int sp = first_space; sp < last_space; sp++) {
229    if (heap->InSpace(heap_obj, static_cast<AllocationSpace>(sp))) {
230      return false;
231    }
232  }
233  SLOW_ASSERT(heap->InSpace(heap_obj, LO_SPACE));
234  return true;
235}
236
237
238static LiveObjectType FindTypeFor(String* type_str) {
239  SmartArrayPointer<char> s =
240      type_str->ToCString(DISALLOW_NULLS, ROBUST_STRING_TRAVERSAL);
241
242#define CHECK_OBJECT_TYPE(type_, name) { \
243    const char* type_desc = GetObjectTypeDesc(kType##type_); \
244    const char* key_str = *s; \
245    if (strstr(type_desc, key_str) != NULL) return kType##type_; \
246  }
247  FOR_EACH_LIVE_OBJECT_TYPE(CHECK_OBJECT_TYPE)
248#undef CHECK_OBJECT_TYPE
249
250  return kInvalidLiveObjType;
251}
252
253
254class LolFilter {
255 public:
256  explicit LolFilter(Handle<JSObject> filter_obj);
257
258  inline bool is_active() const { return is_active_; }
259  inline bool Matches(HeapObject* obj) {
260    return !is_active() || MatchesSlow(obj);
261  }
262
263 private:
264  void InitTypeFilter(Handle<JSObject> filter_obj);
265  void InitSpaceFilter(Handle<JSObject> filter_obj);
266  void InitPropertyFilter(Handle<JSObject> filter_obj);
267  bool MatchesSlow(HeapObject* obj);
268
269  bool is_active_;
270  LiveObjectType type_;
271  AllocationSpace space_;
272  Handle<String> prop_;
273};
274
275
276LolFilter::LolFilter(Handle<JSObject> filter_obj)
277    : is_active_(false),
278      type_(kInvalidLiveObjType),
279      space_(kInvalidSpace),
280      prop_() {
281  if (filter_obj.is_null()) return;
282
283  InitTypeFilter(filter_obj);
284  InitSpaceFilter(filter_obj);
285  InitPropertyFilter(filter_obj);
286}
287
288
289void LolFilter::InitTypeFilter(Handle<JSObject> filter_obj) {
290  Handle<String> type_sym = FACTORY->LookupAsciiSymbol("type");
291  MaybeObject* maybe_result = filter_obj->GetProperty(*type_sym);
292  Object* type_obj;
293  if (maybe_result->ToObject(&type_obj)) {
294    if (type_obj->IsString()) {
295      String* type_str = String::cast(type_obj);
296      type_ = FindTypeFor(type_str);
297      if (type_ != kInvalidLiveObjType) {
298        is_active_ = true;
299      }
300    }
301  }
302}
303
304
305void LolFilter::InitSpaceFilter(Handle<JSObject> filter_obj) {
306  Handle<String> space_sym = FACTORY->LookupAsciiSymbol("space");
307  MaybeObject* maybe_result = filter_obj->GetProperty(*space_sym);
308  Object* space_obj;
309  if (maybe_result->ToObject(&space_obj)) {
310    if (space_obj->IsString()) {
311      String* space_str = String::cast(space_obj);
312      space_ = FindSpaceFor(space_str);
313      if (space_ != kInvalidSpace) {
314        is_active_ = true;
315      }
316    }
317  }
318}
319
320
321void LolFilter::InitPropertyFilter(Handle<JSObject> filter_obj) {
322  Handle<String> prop_sym = FACTORY->LookupAsciiSymbol("prop");
323  MaybeObject* maybe_result = filter_obj->GetProperty(*prop_sym);
324  Object* prop_obj;
325  if (maybe_result->ToObject(&prop_obj)) {
326    if (prop_obj->IsString()) {
327      prop_ = Handle<String>(String::cast(prop_obj));
328      is_active_ = true;
329    }
330  }
331}
332
333
334bool LolFilter::MatchesSlow(HeapObject* obj) {
335  if ((type_ != kInvalidLiveObjType) && !IsOfType(type_, obj)) {
336    return false;  // Fail because obj is not of the type of interest.
337  }
338  if ((space_ != kInvalidSpace) && !InSpace(space_, obj)) {
339    return false;  // Fail because obj is not in the space of interest.
340  }
341  if (!prop_.is_null() && obj->IsJSObject()) {
342    LookupResult result;
343    obj->Lookup(*prop_, &result);
344    if (!result.IsProperty()) {
345      return false;  // Fail because obj does not have the property of interest.
346    }
347  }
348  return true;
349}
350
351
352class LolIterator {
353 public:
354  LolIterator(LiveObjectList* older, LiveObjectList* newer)
355      : older_(older),
356        newer_(newer),
357        curr_(0),
358        elements_(0),
359        count_(0),
360        index_(0) { }
361
362  inline void Init() {
363    SetCurrent(newer_);
364    // If the elements_ list is empty, then move on to the next list as long
365    // as we're not at the last list (indicated by done()).
366    while ((elements_ == NULL) && !Done()) {
367      SetCurrent(curr_->prev_);
368    }
369  }
370
371  inline bool Done() const {
372    return (curr_ == older_);
373  }
374
375  // Object level iteration.
376  inline void Next() {
377    index_++;
378    if (index_ >= count_) {
379      // Iterate backwards until we get to the oldest list.
380      while (!Done()) {
381        SetCurrent(curr_->prev_);
382        // If we have elements to process, we're good to go.
383        if (elements_ != NULL) break;
384
385        // Else, we should advance to the next older list.
386      }
387    }
388  }
389
390  inline int Id() const {
391    return elements_[index_].id_;
392  }
393  inline HeapObject* Obj() const {
394    return elements_[index_].obj_;
395  }
396
397  inline int LolObjCount() const {
398    if (curr_ != NULL) return curr_->obj_count_;
399    return 0;
400  }
401
402 protected:
403  inline void SetCurrent(LiveObjectList* new_curr) {
404    curr_ = new_curr;
405    if (curr_ != NULL) {
406      elements_ = curr_->elements_;
407      count_ = curr_->obj_count_;
408      index_ = 0;
409    }
410  }
411
412  LiveObjectList* older_;
413  LiveObjectList* newer_;
414  LiveObjectList* curr_;
415  LiveObjectList::Element* elements_;
416  int count_;
417  int index_;
418};
419
420
421class LolForwardIterator : public LolIterator {
422 public:
423  LolForwardIterator(LiveObjectList* first, LiveObjectList* last)
424      : LolIterator(first, last) {
425  }
426
427  inline void Init() {
428    SetCurrent(older_);
429    // If the elements_ list is empty, then move on to the next list as long
430    // as we're not at the last list (indicated by Done()).
431    while ((elements_ == NULL) && !Done()) {
432      SetCurrent(curr_->next_);
433    }
434  }
435
436  inline bool Done() const {
437    return (curr_ == newer_);
438  }
439
440  // Object level iteration.
441  inline void Next() {
442    index_++;
443    if (index_ >= count_) {
444      // Done with current list.  Move on to the next.
445      while (!Done()) {  // If not at the last list already, ...
446        SetCurrent(curr_->next_);
447        // If we have elements to process, we're good to go.
448        if (elements_ != NULL) break;
449
450        // Else, we should advance to the next list.
451      }
452    }
453  }
454};
455
456
457// Minimizes the white space in a string.  Tabs and newlines are replaced
458// with a space where appropriate.
459static int CompactString(char* str) {
460  char* src = str;
461  char* dst = str;
462  char prev_ch = 0;
463  while (*dst != '\0') {
464    char ch = *src++;
465    // We will treat non-ASCII chars as '?'.
466    if ((ch & 0x80) != 0) {
467      ch = '?';
468    }
469    // Compact contiguous whitespace chars into a single ' '.
470    if (isspace(ch)) {
471      if (prev_ch != ' ') *dst++ = ' ';
472      prev_ch = ' ';
473      continue;
474    }
475    *dst++ = ch;
476    prev_ch = ch;
477  }
478  return (dst - str);
479}
480
481
482// Generates a custom description based on the specific type of
483// object we're looking at.  We only generate specialized
484// descriptions where we can.  In all other cases, we emit the
485// generic info.
486static void GenerateObjectDesc(HeapObject* obj,
487                               char* buffer,
488                               int buffer_size) {
489  Vector<char> buffer_v(buffer, buffer_size);
490  ASSERT(obj != NULL);
491  if (obj->IsJSArray()) {
492    JSArray* jsarray = JSArray::cast(obj);
493    double length = jsarray->length()->Number();
494    OS::SNPrintF(buffer_v,
495                 "%p <%s> len %g",
496                 reinterpret_cast<void*>(obj),
497                 GetObjectTypeDesc(obj),
498                 length);
499
500  } else if (obj->IsString()) {
501    String* str = String::cast(obj);
502    // Only grab up to 160 chars in case they are double byte.
503    // We'll only dump 80 of them after we compact them.
504    const int kMaxCharToDump = 80;
505    const int kMaxBufferSize = kMaxCharToDump * 2;
506    SmartArrayPointer<char> str_sp = str->ToCString(DISALLOW_NULLS,
507                                                    ROBUST_STRING_TRAVERSAL,
508                                                    0,
509                                                    kMaxBufferSize);
510    char* str_cstr = *str_sp;
511    int length = CompactString(str_cstr);
512    OS::SNPrintF(buffer_v,
513                 "%p <%s> '%.80s%s'",
514                 reinterpret_cast<void*>(obj),
515                 GetObjectTypeDesc(obj),
516                 str_cstr,
517                 (length > kMaxCharToDump) ? "..." : "");
518
519  } else if (obj->IsJSFunction() || obj->IsSharedFunctionInfo()) {
520    SharedFunctionInfo* sinfo;
521    if (obj->IsJSFunction()) {
522      JSFunction* func = JSFunction::cast(obj);
523      sinfo = func->shared();
524    } else {
525      sinfo = SharedFunctionInfo::cast(obj);
526    }
527
528    String* name = sinfo->DebugName();
529    SmartArrayPointer<char> name_sp =
530        name->ToCString(DISALLOW_NULLS, ROBUST_STRING_TRAVERSAL);
531    char* name_cstr = *name_sp;
532
533    HeapStringAllocator string_allocator;
534    StringStream stream(&string_allocator);
535    sinfo->SourceCodePrint(&stream, 50);
536    SmartArrayPointer<const char> source_sp = stream.ToCString();
537    const char* source_cstr = *source_sp;
538
539    OS::SNPrintF(buffer_v,
540                 "%p <%s> '%s' %s",
541                 reinterpret_cast<void*>(obj),
542                 GetObjectTypeDesc(obj),
543                 name_cstr,
544                 source_cstr);
545
546  } else if (obj->IsFixedArray()) {
547    FixedArray* fixed = FixedArray::cast(obj);
548
549    OS::SNPrintF(buffer_v,
550                 "%p <%s> len %d",
551                 reinterpret_cast<void*>(obj),
552                 GetObjectTypeDesc(obj),
553                 fixed->length());
554
555  } else {
556    OS::SNPrintF(buffer_v,
557                 "%p <%s>",
558                 reinterpret_cast<void*>(obj),
559                 GetObjectTypeDesc(obj));
560  }
561}
562
563
564// Utility function for filling in a line of detail in a verbose dump.
565static bool AddObjDetail(Handle<FixedArray> arr,
566                         int index,
567                         int obj_id,
568                         Handle<HeapObject> target,
569                         const char* desc_str,
570                         Handle<String> id_sym,
571                         Handle<String> desc_sym,
572                         Handle<String> size_sym,
573                         Handle<JSObject> detail,
574                         Handle<String> desc,
575                         Handle<Object> error) {
576  Isolate* isolate = Isolate::Current();
577  Factory* factory = isolate->factory();
578  detail = factory->NewJSObject(isolate->object_function());
579  if (detail->IsFailure()) {
580    error = detail;
581    return false;
582  }
583
584  int size = 0;
585  char buffer[512];
586  if (desc_str == NULL) {
587    ASSERT(!target.is_null());
588    HeapObject* obj = *target;
589    GenerateObjectDesc(obj, buffer, sizeof(buffer));
590    desc_str = buffer;
591    size = obj->Size();
592  }
593  desc = factory->NewStringFromAscii(CStrVector(desc_str));
594  if (desc->IsFailure()) {
595    error = desc;
596    return false;
597  }
598
599  { MaybeObject* maybe_result = detail->SetProperty(*id_sym,
600                                                    Smi::FromInt(obj_id),
601                                                    NONE,
602                                                    kNonStrictMode);
603    if (maybe_result->IsFailure()) return false;
604  }
605  { MaybeObject* maybe_result = detail->SetProperty(*desc_sym,
606                                                    *desc,
607                                                    NONE,
608                                                    kNonStrictMode);
609    if (maybe_result->IsFailure()) return false;
610  }
611  { MaybeObject* maybe_result = detail->SetProperty(*size_sym,
612                                                    Smi::FromInt(size),
613                                                    NONE,
614                                                    kNonStrictMode);
615    if (maybe_result->IsFailure()) return false;
616  }
617
618  arr->set(index, *detail);
619  return true;
620}
621
622
623class DumpWriter {
624 public:
625  virtual ~DumpWriter() {}
626
627  virtual void ComputeTotalCountAndSize(LolFilter* filter,
628                                        int* count,
629                                        int* size) = 0;
630  virtual bool Write(Handle<FixedArray> elements_arr,
631                     int start,
632                     int dump_limit,
633                     LolFilter* filter,
634                     Handle<Object> error) = 0;
635};
636
637
638class LolDumpWriter: public DumpWriter {
639 public:
640  LolDumpWriter(LiveObjectList* older, LiveObjectList* newer)
641      : older_(older), newer_(newer) {
642  }
643
644  void ComputeTotalCountAndSize(LolFilter* filter, int* count, int* size) {
645    *count = 0;
646    *size = 0;
647
648    LolIterator it(older_, newer_);
649    for (it.Init(); !it.Done(); it.Next()) {
650      HeapObject* heap_obj = it.Obj();
651      if (!filter->Matches(heap_obj)) {
652        continue;
653      }
654
655      *size += heap_obj->Size();
656      (*count)++;
657    }
658  }
659
660  bool Write(Handle<FixedArray> elements_arr,
661             int start,
662             int dump_limit,
663             LolFilter* filter,
664             Handle<Object> error) {
665    // The lols are listed in latest to earliest.  We want to dump from
666    // earliest to latest.  So, compute the last element to start with.
667    int index = 0;
668    int count = 0;
669
670    Isolate* isolate = Isolate::Current();
671    Factory* factory = isolate->factory();
672
673    // Prefetch some needed symbols.
674    Handle<String> id_sym = factory->LookupAsciiSymbol("id");
675    Handle<String> desc_sym = factory->LookupAsciiSymbol("desc");
676    Handle<String> size_sym = factory->LookupAsciiSymbol("size");
677
678    // Fill the array with the lol object details.
679    Handle<JSObject> detail;
680    Handle<String> desc;
681    Handle<HeapObject> target;
682
683    LiveObjectList* first_lol = (older_ != NULL) ?
684                                older_->next_ : LiveObjectList::first_;
685    LiveObjectList* last_lol = (newer_ != NULL) ? newer_->next_ : NULL;
686
687    LolForwardIterator it(first_lol, last_lol);
688    for (it.Init(); !it.Done() && (index < dump_limit); it.Next()) {
689      HeapObject* heap_obj = it.Obj();
690
691      // Skip objects that have been filtered out.
692      if (!filter->Matches(heap_obj)) {
693        continue;
694      }
695
696      // Only report objects that are in the section of interest.
697      if (count >= start) {
698        target = Handle<HeapObject>(heap_obj);
699        bool success = AddObjDetail(elements_arr,
700                                    index++,
701                                    it.Id(),
702                                    target,
703                                    NULL,
704                                    id_sym,
705                                    desc_sym,
706                                    size_sym,
707                                    detail,
708                                    desc,
709                                    error);
710        if (!success) return false;
711      }
712      count++;
713    }
714    return true;
715  }
716
717 private:
718  LiveObjectList* older_;
719  LiveObjectList* newer_;
720};
721
722
723class RetainersDumpWriter: public DumpWriter {
724 public:
725  RetainersDumpWriter(Handle<HeapObject> target,
726                      Handle<JSObject> instance_filter,
727                      Handle<JSFunction> args_function)
728      : target_(target),
729        instance_filter_(instance_filter),
730        args_function_(args_function) {
731  }
732
733  void ComputeTotalCountAndSize(LolFilter* filter, int* count, int* size) {
734    Handle<FixedArray> retainers_arr;
735    Handle<Object> error;
736
737    *size = -1;
738    LiveObjectList::GetRetainers(target_,
739                                 instance_filter_,
740                                 retainers_arr,
741                                 0,
742                                 Smi::kMaxValue,
743                                 count,
744                                 filter,
745                                 NULL,
746                                 *args_function_,
747                                 error);
748  }
749
750  bool Write(Handle<FixedArray> elements_arr,
751             int start,
752             int dump_limit,
753             LolFilter* filter,
754             Handle<Object> error) {
755    int dummy;
756    int count;
757
758    // Fill the retainer objects.
759    count = LiveObjectList::GetRetainers(target_,
760                                         instance_filter_,
761                                         elements_arr,
762                                         start,
763                                         dump_limit,
764                                         &dummy,
765                                         filter,
766                                         NULL,
767                                         *args_function_,
768                                         error);
769    if (count < 0) {
770        return false;
771    }
772    return true;
773  }
774
775 private:
776  Handle<HeapObject> target_;
777  Handle<JSObject> instance_filter_;
778  Handle<JSFunction> args_function_;
779};
780
781
782class LiveObjectSummary {
783 public:
784  explicit LiveObjectSummary(LolFilter* filter)
785      : total_count_(0),
786        total_size_(0),
787        found_root_(false),
788        found_weak_root_(false),
789        filter_(filter) {
790    memset(counts_, 0, sizeof(counts_[0]) * kNumberOfEntries);
791    memset(sizes_, 0, sizeof(sizes_[0]) * kNumberOfEntries);
792  }
793
794  void Add(HeapObject* heap_obj) {
795    int size = heap_obj->Size();
796    LiveObjectType type = GetObjectType(heap_obj);
797    ASSERT(type != kInvalidLiveObjType);
798    counts_[type]++;
799    sizes_[type] += size;
800    total_count_++;
801    total_size_ += size;
802  }
803
804  void set_found_root() { found_root_ = true; }
805  void set_found_weak_root() { found_weak_root_ = true; }
806
807  inline int Count(LiveObjectType type) {
808    return counts_[type];
809  }
810  inline int Size(LiveObjectType type) {
811    return sizes_[type];
812  }
813  inline int total_count() {
814    return total_count_;
815  }
816  inline int total_size() {
817    return total_size_;
818  }
819  inline bool found_root() {
820    return found_root_;
821  }
822  inline bool found_weak_root() {
823    return found_weak_root_;
824  }
825  int GetNumberOfEntries() {
826    int entries = 0;
827    for (int i = 0; i < kNumberOfEntries; i++) {
828      if (counts_[i]) entries++;
829    }
830    return entries;
831  }
832
833  inline LolFilter* filter() { return filter_; }
834
835  static const int kNumberOfEntries = kNumberOfTypes;
836
837 private:
838  int counts_[kNumberOfEntries];
839  int sizes_[kNumberOfEntries];
840  int total_count_;
841  int total_size_;
842  bool found_root_;
843  bool found_weak_root_;
844
845  LolFilter* filter_;
846};
847
848
849// Abstraction for a summary writer.
850class SummaryWriter {
851 public:
852  virtual ~SummaryWriter() {}
853  virtual void Write(LiveObjectSummary* summary) = 0;
854};
855
856
857// A summary writer for filling in a summary of lol lists and diffs.
858class LolSummaryWriter: public SummaryWriter {
859 public:
860  LolSummaryWriter(LiveObjectList* older_lol,
861                   LiveObjectList* newer_lol)
862      : older_(older_lol), newer_(newer_lol) {
863  }
864
865  void Write(LiveObjectSummary* summary) {
866    LolFilter* filter = summary->filter();
867
868    // Fill the summary with the lol object details.
869    LolIterator it(older_, newer_);
870    for (it.Init(); !it.Done(); it.Next()) {
871      HeapObject* heap_obj = it.Obj();
872      if (!filter->Matches(heap_obj)) {
873        continue;
874      }
875      summary->Add(heap_obj);
876    }
877  }
878
879 private:
880  LiveObjectList* older_;
881  LiveObjectList* newer_;
882};
883
884
885// A summary writer for filling in a retainers list.
886class RetainersSummaryWriter: public SummaryWriter {
887 public:
888  RetainersSummaryWriter(Handle<HeapObject> target,
889                         Handle<JSObject> instance_filter,
890                         Handle<JSFunction> args_function)
891      : target_(target),
892        instance_filter_(instance_filter),
893        args_function_(args_function) {
894  }
895
896  void Write(LiveObjectSummary* summary) {
897    Handle<FixedArray> retainers_arr;
898    Handle<Object> error;
899    int dummy_total_count;
900    LiveObjectList::GetRetainers(target_,
901                                 instance_filter_,
902                                 retainers_arr,
903                                 0,
904                                 Smi::kMaxValue,
905                                 &dummy_total_count,
906                                 summary->filter(),
907                                 summary,
908                                 *args_function_,
909                                 error);
910  }
911
912 private:
913  Handle<HeapObject> target_;
914  Handle<JSObject> instance_filter_;
915  Handle<JSFunction> args_function_;
916};
917
918
919uint32_t LiveObjectList::next_element_id_ = 1;
920int LiveObjectList::list_count_ = 0;
921int LiveObjectList::last_id_ = 0;
922LiveObjectList* LiveObjectList::first_ = NULL;
923LiveObjectList* LiveObjectList::last_ = NULL;
924
925
926LiveObjectList::LiveObjectList(LiveObjectList* prev, int capacity)
927    : prev_(prev),
928      next_(NULL),
929      capacity_(capacity),
930      obj_count_(0) {
931  elements_ = NewArray<Element>(capacity);
932  id_ = ++last_id_;
933
934  list_count_++;
935}
936
937
938LiveObjectList::~LiveObjectList() {
939  DeleteArray<Element>(elements_);
940  delete prev_;
941}
942
943
944int LiveObjectList::GetTotalObjCountAndSize(int* size_p) {
945  int size = 0;
946  int count = 0;
947  LiveObjectList* lol = this;
948  do {
949    // Only compute total size if requested i.e. when size_p is not null.
950    if (size_p != NULL) {
951      Element* elements = lol->elements_;
952      for (int i = 0; i < lol->obj_count_; i++) {
953        HeapObject* heap_obj = elements[i].obj_;
954        size += heap_obj->Size();
955      }
956    }
957    count += lol->obj_count_;
958    lol = lol->prev_;
959  } while (lol != NULL);
960
961  if (size_p != NULL) {
962    *size_p = size;
963  }
964  return count;
965}
966
967
968// Adds an object to the lol.
969// Returns true if successful, else returns false.
970bool LiveObjectList::Add(HeapObject* obj) {
971  // If the object is already accounted for in the prev list which we inherit
972  // from, then no need to add it to this list.
973  if ((prev() != NULL) && (prev()->Find(obj) != NULL)) {
974    return true;
975  }
976  ASSERT(obj_count_ <= capacity_);
977  if (obj_count_ == capacity_) {
978    // The heap must have grown and we have more objects than capacity to store
979    // them.
980    return false;  // Fail this addition.
981  }
982  Element& element = elements_[obj_count_++];
983  element.id_ = next_element_id_++;
984  element.obj_ = obj;
985  return true;
986}
987
988
989// Comparator used for sorting and searching the lol.
990int LiveObjectList::CompareElement(const Element* a, const Element* b) {
991  const HeapObject* obj1 = a->obj_;
992  const HeapObject* obj2 = b->obj_;
993  // For lol elements, it doesn't matter which comes first if 2 elements point
994  // to the same object (which gets culled later).  Hence, we only care about
995  // the the greater than / less than relationships.
996  return (obj1 > obj2) ? 1 : (obj1 == obj2) ? 0 : -1;
997}
998
999
1000// Looks for the specified object in the lol, and returns its element if found.
1001LiveObjectList::Element* LiveObjectList::Find(HeapObject* obj) {
1002  LiveObjectList* lol = this;
1003  Element key;
1004  Element* result = NULL;
1005
1006  key.obj_ = obj;
1007  // Iterate through the chain of lol's to look for the object.
1008  while ((result == NULL) && (lol != NULL)) {
1009    result = reinterpret_cast<Element*>(
1010        bsearch(&key, lol->elements_, lol->obj_count_,
1011                sizeof(Element),
1012                reinterpret_cast<RawComparer>(CompareElement)));
1013    lol = lol->prev_;
1014  }
1015  return result;
1016}
1017
1018
1019// "Nullifies" (convert the HeapObject* into an SMI) so that it will get cleaned
1020// up in the GCEpilogue, while preserving the sort order of the lol.
1021// NOTE: the lols need to be already sorted before NullifyMostRecent() is
1022// called.
1023void LiveObjectList::NullifyMostRecent(HeapObject* obj) {
1024  LiveObjectList* lol = last();
1025  Element key;
1026  Element* result = NULL;
1027
1028  key.obj_ = obj;
1029  // Iterate through the chain of lol's to look for the object.
1030  while (lol != NULL) {
1031    result = reinterpret_cast<Element*>(
1032        bsearch(&key, lol->elements_, lol->obj_count_,
1033                sizeof(Element),
1034                reinterpret_cast<RawComparer>(CompareElement)));
1035    if (result != NULL) {
1036      // Since there may be more than one (we are nullifying dup's after all),
1037      // find the first in the current lol, and nullify that.  The lol should
1038      // be sorted already to make this easy (see the use of SortAll()).
1039      int i = result - lol->elements_;
1040
1041      // NOTE: we sort the lol in increasing order.  So, if an object has been
1042      // "nullified" (its lowest bit will be cleared to make it look like an
1043      // SMI), it would/should show up before the equivalent dups that have not
1044      // yet been "nullified".  Hence, we should be searching backwards for the
1045      // first occurence of a matching object and nullify that instance.  This
1046      // will ensure that we preserve the expected sorting order.
1047      for (i--; i > 0; i--) {
1048        Element* element = &lol->elements_[i];
1049        HeapObject* curr_obj = element->obj_;
1050        if (curr_obj != obj) {
1051            break;  // No more matches.  Let's move on.
1052        }
1053        result = element;  // Let this earlier match be the result.
1054      }
1055
1056      // Nullify the object.
1057      NullifyNonLivePointer(&result->obj_);
1058      return;
1059    }
1060    lol = lol->prev_;
1061  }
1062}
1063
1064
1065// Sorts the lol.
1066void LiveObjectList::Sort() {
1067  if (obj_count_ > 0) {
1068    Vector<Element> elements_v(elements_, obj_count_);
1069    elements_v.Sort(CompareElement);
1070  }
1071}
1072
1073
1074// Sorts all captured lols starting from the latest.
1075void LiveObjectList::SortAll() {
1076  LiveObjectList* lol = last();
1077  while (lol != NULL) {
1078    lol->Sort();
1079    lol = lol->prev_;
1080  }
1081}
1082
1083
1084// Counts the number of objects in the heap.
1085static int CountHeapObjects() {
1086  int count = 0;
1087  // Iterate over all the heap spaces and count the number of objects.
1088  HeapIterator iterator;
1089  HeapObject* heap_obj = NULL;
1090  while ((heap_obj = iterator.next()) != NULL) {
1091    count++;
1092  }
1093  return count;
1094}
1095
1096
1097// Captures a current snapshot of all objects in the heap.
1098MaybeObject* LiveObjectList::Capture() {
1099  Isolate* isolate = Isolate::Current();
1100  Factory* factory = isolate->factory();
1101  HandleScope scope(isolate);
1102
1103  // Count the number of objects in the heap.
1104  int total_count = CountHeapObjects();
1105  int count = total_count;
1106  int size = 0;
1107
1108  LiveObjectList* last_lol = last();
1109  if (last_lol != NULL) {
1110    count -= last_lol->TotalObjCount();
1111  }
1112
1113  LiveObjectList* lol;
1114
1115  // Create a lol large enough to track all the objects.
1116  lol = new LiveObjectList(last_lol, count);
1117  if (lol == NULL) {
1118    return NULL;  // No memory to proceed.
1119  }
1120
1121  // The HeapIterator needs to be in its own scope because it disables
1122  // allocation, and we need allocate below.
1123  {
1124    // Iterate over all the heap spaces and add the objects.
1125    HeapIterator iterator;
1126    HeapObject* heap_obj = NULL;
1127    bool failed = false;
1128    while (!failed && (heap_obj = iterator.next()) != NULL) {
1129      failed = !lol->Add(heap_obj);
1130      size += heap_obj->Size();
1131    }
1132    ASSERT(!failed);
1133
1134    lol->Sort();
1135
1136    // Add the current lol to the list of lols.
1137    if (last_ != NULL) {
1138      last_->next_ = lol;
1139    } else {
1140      first_ = lol;
1141    }
1142    last_ = lol;
1143
1144#ifdef VERIFY_LOL
1145    if (FLAG_verify_lol) {
1146      Verify(true);
1147    }
1148#endif
1149  }
1150
1151  Handle<String> id_sym = factory->LookupAsciiSymbol("id");
1152  Handle<String> count_sym = factory->LookupAsciiSymbol("count");
1153  Handle<String> size_sym = factory->LookupAsciiSymbol("size");
1154
1155  Handle<JSObject> result = factory->NewJSObject(isolate->object_function());
1156  if (result->IsFailure()) return Object::cast(*result);
1157
1158  { MaybeObject* maybe_result = result->SetProperty(*id_sym,
1159                                                    Smi::FromInt(lol->id()),
1160                                                    NONE,
1161                                                    kNonStrictMode);
1162    if (maybe_result->IsFailure()) return maybe_result;
1163  }
1164  { MaybeObject* maybe_result = result->SetProperty(*count_sym,
1165                                                    Smi::FromInt(total_count),
1166                                                    NONE,
1167                                                    kNonStrictMode);
1168    if (maybe_result->IsFailure()) return maybe_result;
1169  }
1170  { MaybeObject* maybe_result = result->SetProperty(*size_sym,
1171                                                    Smi::FromInt(size),
1172                                                    NONE,
1173                                                    kNonStrictMode);
1174    if (maybe_result->IsFailure()) return maybe_result;
1175  }
1176
1177  return *result;
1178}
1179
1180
1181// Delete doesn't actually deletes an lol.  It just marks it as invisible since
1182// its contents are considered to be part of subsequent lists as well.  The
1183// only time we'll actually delete the lol is when we Reset() or if the lol is
1184// invisible, and its element count reaches 0.
1185bool LiveObjectList::Delete(int id) {
1186  LiveObjectList* lol = last();
1187  while (lol != NULL) {
1188    if (lol->id() == id) {
1189      break;
1190    }
1191    lol = lol->prev_;
1192  }
1193
1194  // If no lol is found for this id, then we fail to delete.
1195  if (lol == NULL) return false;
1196
1197  // Else, mark the lol as invisible i.e. id == 0.
1198  lol->id_ = 0;
1199  list_count_--;
1200  ASSERT(list_count_ >= 0);
1201  if (lol->obj_count_ == 0) {
1202    // Point the next lol's prev to this lol's prev.
1203    LiveObjectList* next = lol->next_;
1204    LiveObjectList* prev = lol->prev_;
1205    // Point next's prev to prev.
1206    if (next != NULL) {
1207      next->prev_ = lol->prev_;
1208    } else {
1209      last_ = lol->prev_;
1210    }
1211    // Point prev's next to next.
1212    if (prev != NULL) {
1213      prev->next_ = lol->next_;
1214    } else {
1215      first_ = lol->next_;
1216    }
1217
1218    lol->prev_ = NULL;
1219    lol->next_ = NULL;
1220
1221    // Delete this now empty and invisible lol.
1222    delete lol;
1223  }
1224
1225  // Just in case we've marked everything invisible, then clean up completely.
1226  if (list_count_ == 0) {
1227    Reset();
1228  }
1229
1230  return true;
1231}
1232
1233
1234MaybeObject* LiveObjectList::Dump(int older_id,
1235                                  int newer_id,
1236                                  int start_idx,
1237                                  int dump_limit,
1238                                  Handle<JSObject> filter_obj) {
1239  if ((older_id < 0) || (newer_id < 0) || (last() == NULL)) {
1240    return Failure::Exception();  // Fail: 0 is not a valid lol id.
1241  }
1242  if (newer_id < older_id) {
1243    // They are not in the expected order.  Swap them.
1244    int temp = older_id;
1245    older_id = newer_id;
1246    newer_id = temp;
1247  }
1248
1249  LiveObjectList* newer_lol = FindLolForId(newer_id, last());
1250  LiveObjectList* older_lol = FindLolForId(older_id, newer_lol);
1251
1252  // If the id is defined, and we can't find a LOL for it, then we have an
1253  // invalid id.
1254  if ((newer_id != 0) && (newer_lol == NULL)) {
1255    return Failure::Exception();  // Fail: the newer lol id is invalid.
1256  }
1257  if ((older_id != 0) && (older_lol == NULL)) {
1258    return Failure::Exception();  // Fail: the older lol id is invalid.
1259  }
1260
1261  LolFilter filter(filter_obj);
1262  LolDumpWriter writer(older_lol, newer_lol);
1263  return DumpPrivate(&writer, start_idx, dump_limit, &filter);
1264}
1265
1266
1267MaybeObject* LiveObjectList::DumpPrivate(DumpWriter* writer,
1268                                         int start,
1269                                         int dump_limit,
1270                                         LolFilter* filter) {
1271  Isolate* isolate = Isolate::Current();
1272  Factory* factory = isolate->factory();
1273
1274  HandleScope scope(isolate);
1275
1276  // Calculate the number of entries of the dump.
1277  int count = -1;
1278  int size = -1;
1279  writer->ComputeTotalCountAndSize(filter, &count, &size);
1280
1281  // Adjust for where to start the dump.
1282  if ((start < 0) || (start >= count)) {
1283    return Failure::Exception();  // invalid start.
1284  }
1285
1286  int remaining_count = count - start;
1287  if (dump_limit > remaining_count) {
1288    dump_limit = remaining_count;
1289  }
1290
1291  // Allocate an array to hold the result.
1292  Handle<FixedArray> elements_arr = factory->NewFixedArray(dump_limit);
1293  if (elements_arr->IsFailure()) return Object::cast(*elements_arr);
1294
1295  // Fill in the dump.
1296  Handle<Object> error;
1297  bool success = writer->Write(elements_arr,
1298                               start,
1299                               dump_limit,
1300                               filter,
1301                               error);
1302  if (!success) return Object::cast(*error);
1303
1304  MaybeObject* maybe_result;
1305
1306  // Allocate the result body.
1307  Handle<JSObject> body = factory->NewJSObject(isolate->object_function());
1308  if (body->IsFailure()) return Object::cast(*body);
1309
1310  // Set the updated body.count.
1311  Handle<String> count_sym = factory->LookupAsciiSymbol("count");
1312  maybe_result = body->SetProperty(*count_sym,
1313                                   Smi::FromInt(count),
1314                                   NONE,
1315                                   kNonStrictMode);
1316  if (maybe_result->IsFailure()) return maybe_result;
1317
1318  // Set the updated body.size if appropriate.
1319  if (size >= 0) {
1320    Handle<String> size_sym = factory->LookupAsciiSymbol("size");
1321    maybe_result = body->SetProperty(*size_sym,
1322                                     Smi::FromInt(size),
1323                                     NONE,
1324                                     kNonStrictMode);
1325    if (maybe_result->IsFailure()) return maybe_result;
1326  }
1327
1328  // Set body.first_index.
1329  Handle<String> first_sym = factory->LookupAsciiSymbol("first_index");
1330  maybe_result = body->SetProperty(*first_sym,
1331                                   Smi::FromInt(start),
1332                                   NONE,
1333                                   kNonStrictMode);
1334  if (maybe_result->IsFailure()) return maybe_result;
1335
1336  // Allocate the JSArray of the elements.
1337  Handle<JSObject> elements = factory->NewJSObject(isolate->array_function());
1338  if (elements->IsFailure()) return Object::cast(*elements);
1339
1340  maybe_result = Handle<JSArray>::cast(elements)->SetContent(*elements_arr);
1341  if (maybe_result->IsFailure()) return maybe_result;
1342
1343  // Set body.elements.
1344  Handle<String> elements_sym = factory->LookupAsciiSymbol("elements");
1345  maybe_result = body->SetProperty(*elements_sym,
1346                                   *elements,
1347                                   NONE,
1348                                   kNonStrictMode);
1349  if (maybe_result->IsFailure()) return maybe_result;
1350
1351  return *body;
1352}
1353
1354
1355MaybeObject* LiveObjectList::Summarize(int older_id,
1356                                       int newer_id,
1357                                       Handle<JSObject> filter_obj) {
1358  if ((older_id < 0) || (newer_id < 0) || (last() == NULL)) {
1359    return Failure::Exception();  // Fail: 0 is not a valid lol id.
1360  }
1361  if (newer_id < older_id) {
1362    // They are not in the expected order.  Swap them.
1363    int temp = older_id;
1364    older_id = newer_id;
1365    newer_id = temp;
1366  }
1367
1368  LiveObjectList* newer_lol = FindLolForId(newer_id, last());
1369  LiveObjectList* older_lol = FindLolForId(older_id, newer_lol);
1370
1371  // If the id is defined, and we can't find a LOL for it, then we have an
1372  // invalid id.
1373  if ((newer_id != 0) && (newer_lol == NULL)) {
1374    return Failure::Exception();  // Fail: the newer lol id is invalid.
1375  }
1376  if ((older_id != 0) && (older_lol == NULL)) {
1377    return Failure::Exception();  // Fail: the older lol id is invalid.
1378  }
1379
1380  LolFilter filter(filter_obj);
1381  LolSummaryWriter writer(older_lol, newer_lol);
1382  return SummarizePrivate(&writer, &filter, false);
1383}
1384
1385
1386// Creates a summary report for the debugger.
1387// Note: the SummaryWriter takes care of iterating over objects and filling in
1388// the summary.
1389MaybeObject* LiveObjectList::SummarizePrivate(SummaryWriter* writer,
1390                                              LolFilter* filter,
1391                                              bool is_tracking_roots) {
1392  HandleScope scope;
1393  MaybeObject* maybe_result;
1394
1395  LiveObjectSummary summary(filter);
1396  writer->Write(&summary);
1397
1398  Isolate* isolate = Isolate::Current();
1399  Factory* factory = isolate->factory();
1400
1401  // The result body will look like this:
1402  // body: {
1403  //   count: <total_count>,
1404  //   size: <total_size>,
1405  //   found_root: <boolean>,       // optional.
1406  //   found_weak_root: <boolean>,  // optional.
1407  //   summary: [
1408  //     {
1409  //       desc: "<object type name>",
1410  //       count: <count>,
1411  //       size: size
1412  //     },
1413  //     ...
1414  //   ]
1415  // }
1416
1417  // Prefetch some needed symbols.
1418  Handle<String> desc_sym = factory->LookupAsciiSymbol("desc");
1419  Handle<String> count_sym = factory->LookupAsciiSymbol("count");
1420  Handle<String> size_sym = factory->LookupAsciiSymbol("size");
1421  Handle<String> summary_sym = factory->LookupAsciiSymbol("summary");
1422
1423  // Allocate the summary array.
1424  int entries_count = summary.GetNumberOfEntries();
1425  Handle<FixedArray> summary_arr =
1426      factory->NewFixedArray(entries_count);
1427  if (summary_arr->IsFailure()) return Object::cast(*summary_arr);
1428
1429  int idx = 0;
1430  for (int i = 0; i < LiveObjectSummary::kNumberOfEntries; i++) {
1431    // Allocate the summary record.
1432    Handle<JSObject> detail = factory->NewJSObject(isolate->object_function());
1433    if (detail->IsFailure()) return Object::cast(*detail);
1434
1435    // Fill in the summary record.
1436    LiveObjectType type = static_cast<LiveObjectType>(i);
1437    int count = summary.Count(type);
1438    if (count) {
1439      const char* desc_cstr = GetObjectTypeDesc(type);
1440      Handle<String> desc = factory->LookupAsciiSymbol(desc_cstr);
1441      int size = summary.Size(type);
1442
1443      maybe_result = detail->SetProperty(*desc_sym,
1444                                         *desc,
1445                                         NONE,
1446                                         kNonStrictMode);
1447      if (maybe_result->IsFailure()) return maybe_result;
1448      maybe_result = detail->SetProperty(*count_sym,
1449                                         Smi::FromInt(count),
1450                                         NONE,
1451                                         kNonStrictMode);
1452      if (maybe_result->IsFailure()) return maybe_result;
1453      maybe_result = detail->SetProperty(*size_sym,
1454                                         Smi::FromInt(size),
1455                                         NONE,
1456                                         kNonStrictMode);
1457      if (maybe_result->IsFailure()) return maybe_result;
1458
1459      summary_arr->set(idx++, *detail);
1460    }
1461  }
1462
1463  // Wrap the summary fixed array in a JS array.
1464  Handle<JSObject> summary_obj =
1465    factory->NewJSObject(isolate->array_function());
1466  if (summary_obj->IsFailure()) return Object::cast(*summary_obj);
1467
1468  maybe_result = Handle<JSArray>::cast(summary_obj)->SetContent(*summary_arr);
1469  if (maybe_result->IsFailure()) return maybe_result;
1470
1471  // Create the body object.
1472  Handle<JSObject> body = factory->NewJSObject(isolate->object_function());
1473  if (body->IsFailure()) return Object::cast(*body);
1474
1475  // Fill out the body object.
1476  int total_count = summary.total_count();
1477  int total_size = summary.total_size();
1478  maybe_result = body->SetProperty(*count_sym,
1479                                   Smi::FromInt(total_count),
1480                                   NONE,
1481                                   kNonStrictMode);
1482  if (maybe_result->IsFailure()) return maybe_result;
1483
1484  maybe_result = body->SetProperty(*size_sym,
1485                                   Smi::FromInt(total_size),
1486                                   NONE,
1487                                   kNonStrictMode);
1488  if (maybe_result->IsFailure()) return maybe_result;
1489
1490  if (is_tracking_roots) {
1491    int found_root = summary.found_root();
1492    int found_weak_root = summary.found_weak_root();
1493    Handle<String> root_sym = factory->LookupAsciiSymbol("found_root");
1494    Handle<String> weak_root_sym =
1495        factory->LookupAsciiSymbol("found_weak_root");
1496    maybe_result = body->SetProperty(*root_sym,
1497                                     Smi::FromInt(found_root),
1498                                     NONE,
1499                                     kNonStrictMode);
1500    if (maybe_result->IsFailure()) return maybe_result;
1501    maybe_result = body->SetProperty(*weak_root_sym,
1502                                     Smi::FromInt(found_weak_root),
1503                                     NONE,
1504                                     kNonStrictMode);
1505    if (maybe_result->IsFailure()) return maybe_result;
1506  }
1507
1508  maybe_result = body->SetProperty(*summary_sym,
1509                                   *summary_obj,
1510                                   NONE,
1511                                   kNonStrictMode);
1512  if (maybe_result->IsFailure()) return maybe_result;
1513
1514  return *body;
1515}
1516
1517
1518// Returns an array listing the captured lols.
1519// Note: only dumps the section starting at start_idx and only up to
1520// dump_limit entries.
1521MaybeObject* LiveObjectList::Info(int start_idx, int dump_limit) {
1522  Isolate* isolate = Isolate::Current();
1523  Factory* factory = isolate->factory();
1524
1525  HandleScope scope(isolate);
1526  MaybeObject* maybe_result;
1527
1528  int total_count = LiveObjectList::list_count();
1529  int dump_count = total_count;
1530
1531  // Adjust for where to start the dump.
1532  if (total_count == 0) {
1533      start_idx = 0;  // Ensure this to get an empty list.
1534  } else if ((start_idx < 0) || (start_idx >= total_count)) {
1535    return Failure::Exception();  // invalid start.
1536  }
1537  dump_count -= start_idx;
1538
1539  // Adjust for the dump limit.
1540  if (dump_count > dump_limit) {
1541    dump_count = dump_limit;
1542  }
1543
1544  // Allocate an array to hold the result.
1545  Handle<FixedArray> list = factory->NewFixedArray(dump_count);
1546  if (list->IsFailure()) return Object::cast(*list);
1547
1548  // Prefetch some needed symbols.
1549  Handle<String> id_sym = factory->LookupAsciiSymbol("id");
1550  Handle<String> count_sym = factory->LookupAsciiSymbol("count");
1551  Handle<String> size_sym = factory->LookupAsciiSymbol("size");
1552
1553  // Fill the array with the lol details.
1554  int idx = 0;
1555  LiveObjectList* lol = first_;
1556  while ((lol != NULL) && (idx < start_idx)) {  // Skip tail entries.
1557    if (lol->id() != 0) {
1558      idx++;
1559    }
1560    lol = lol->next();
1561  }
1562  idx = 0;
1563  while ((lol != NULL) && (dump_limit != 0)) {
1564    if (lol->id() != 0) {
1565      int count;
1566      int size;
1567      count = lol->GetTotalObjCountAndSize(&size);
1568
1569      Handle<JSObject> detail =
1570          factory->NewJSObject(isolate->object_function());
1571      if (detail->IsFailure()) return Object::cast(*detail);
1572
1573      maybe_result = detail->SetProperty(*id_sym,
1574                                         Smi::FromInt(lol->id()),
1575                                         NONE,
1576                                         kNonStrictMode);
1577      if (maybe_result->IsFailure()) return maybe_result;
1578      maybe_result = detail->SetProperty(*count_sym,
1579                                         Smi::FromInt(count),
1580                                         NONE,
1581                                         kNonStrictMode);
1582      if (maybe_result->IsFailure()) return maybe_result;
1583      maybe_result = detail->SetProperty(*size_sym,
1584                                         Smi::FromInt(size),
1585                                         NONE,
1586                                         kNonStrictMode);
1587      if (maybe_result->IsFailure()) return maybe_result;
1588      list->set(idx++, *detail);
1589      dump_limit--;
1590    }
1591    lol = lol->next();
1592  }
1593
1594  // Return the result as a JS array.
1595  Handle<JSObject> lols = factory->NewJSObject(isolate->array_function());
1596
1597  maybe_result = Handle<JSArray>::cast(lols)->SetContent(*list);
1598  if (maybe_result->IsFailure()) return maybe_result;
1599
1600  Handle<JSObject> result = factory->NewJSObject(isolate->object_function());
1601  if (result->IsFailure()) return Object::cast(*result);
1602
1603  maybe_result = result->SetProperty(*count_sym,
1604                                     Smi::FromInt(total_count),
1605                                     NONE,
1606                                     kNonStrictMode);
1607  if (maybe_result->IsFailure()) return maybe_result;
1608
1609  Handle<String> first_sym = factory->LookupAsciiSymbol("first_index");
1610  maybe_result = result->SetProperty(*first_sym,
1611                                     Smi::FromInt(start_idx),
1612                                     NONE,
1613                                     kNonStrictMode);
1614  if (maybe_result->IsFailure()) return maybe_result;
1615
1616  Handle<String> lists_sym = factory->LookupAsciiSymbol("lists");
1617  maybe_result = result->SetProperty(*lists_sym,
1618                                     *lols,
1619                                     NONE,
1620                                     kNonStrictMode);
1621  if (maybe_result->IsFailure()) return maybe_result;
1622
1623  return *result;
1624}
1625
1626
1627// Deletes all captured lols.
1628void LiveObjectList::Reset() {
1629  LiveObjectList* lol = last();
1630  // Just delete the last.  Each lol will delete it's prev automatically.
1631  delete lol;
1632
1633  next_element_id_ = 1;
1634  list_count_ = 0;
1635  last_id_ = 0;
1636  first_ = NULL;
1637  last_ = NULL;
1638}
1639
1640
1641// Gets the object for the specified obj id.
1642Object* LiveObjectList::GetObj(int obj_id) {
1643  Element* element = FindElementFor<int>(GetElementId, obj_id);
1644  if (element != NULL) {
1645    return Object::cast(element->obj_);
1646  }
1647  return HEAP->undefined_value();
1648}
1649
1650
1651// Gets the obj id for the specified address if valid.
1652int LiveObjectList::GetObjId(Object* obj) {
1653  // Make a heap object pointer from the address.
1654  HeapObject* hobj = HeapObject::cast(obj);
1655  Element* element = FindElementFor<HeapObject*>(GetElementObj, hobj);
1656  if (element != NULL) {
1657    return element->id_;
1658  }
1659  return 0;  // Invalid address.
1660}
1661
1662
1663// Gets the obj id for the specified address if valid.
1664Object* LiveObjectList::GetObjId(Handle<String> address) {
1665  SmartArrayPointer<char> addr_str =
1666      address->ToCString(DISALLOW_NULLS, ROBUST_STRING_TRAVERSAL);
1667
1668  Isolate* isolate = Isolate::Current();
1669
1670  // Extract the address value from the string.
1671  int value =
1672      static_cast<int>(StringToInt(isolate->unicode_cache(), *address, 16));
1673  Object* obj = reinterpret_cast<Object*>(value);
1674  return Smi::FromInt(GetObjId(obj));
1675}
1676
1677
1678// Helper class for copying HeapObjects.
1679class LolVisitor: public ObjectVisitor {
1680 public:
1681  LolVisitor(HeapObject* target, Handle<HeapObject> handle_to_skip)
1682      : target_(target), handle_to_skip_(handle_to_skip), found_(false) {}
1683
1684  void VisitPointer(Object** p) { CheckPointer(p); }
1685
1686  void VisitPointers(Object** start, Object** end) {
1687    // Check all HeapObject pointers in [start, end).
1688    for (Object** p = start; !found() && p < end; p++) CheckPointer(p);
1689  }
1690
1691  inline bool found() const { return found_; }
1692  inline bool reset() { return found_ = false; }
1693
1694 private:
1695  inline void CheckPointer(Object** p) {
1696    Object* object = *p;
1697    if (HeapObject::cast(object) == target_) {
1698      // We may want to skip this handle because the handle may be a local
1699      // handle in a handle scope in one of our callers.  Once we return,
1700      // that handle will be popped.  Hence, we don't want to count it as
1701      // a root that would have kept the target object alive.
1702      if (!handle_to_skip_.is_null() &&
1703          handle_to_skip_.location() == reinterpret_cast<HeapObject**>(p)) {
1704        return;  // Skip this handle.
1705      }
1706      found_ = true;
1707    }
1708  }
1709
1710  HeapObject* target_;
1711  Handle<HeapObject> handle_to_skip_;
1712  bool found_;
1713};
1714
1715
1716inline bool AddRootRetainerIfFound(const LolVisitor& visitor,
1717                                   LolFilter* filter,
1718                                   LiveObjectSummary* summary,
1719                                   void (*SetRootFound)(LiveObjectSummary* s),
1720                                   int start,
1721                                   int dump_limit,
1722                                   int* total_count,
1723                                   Handle<FixedArray> retainers_arr,
1724                                   int* count,
1725                                   int* index,
1726                                   const char* root_name,
1727                                   Handle<String> id_sym,
1728                                   Handle<String> desc_sym,
1729                                   Handle<String> size_sym,
1730                                   Handle<Object> error) {
1731  HandleScope scope;
1732
1733  // Scratch handles.
1734  Handle<JSObject> detail;
1735  Handle<String> desc;
1736  Handle<HeapObject> retainer;
1737
1738  if (visitor.found()) {
1739    if (!filter->is_active()) {
1740      (*total_count)++;
1741      if (summary) {
1742        SetRootFound(summary);
1743      } else if ((*total_count > start) && ((*index) < dump_limit)) {
1744        (*count)++;
1745        if (!retainers_arr.is_null()) {
1746          return AddObjDetail(retainers_arr,
1747                              (*index)++,
1748                              0,
1749                              retainer,
1750                              root_name,
1751                              id_sym,
1752                              desc_sym,
1753                              size_sym,
1754                              detail,
1755                              desc,
1756                              error);
1757        }
1758      }
1759    }
1760  }
1761  return true;
1762}
1763
1764
1765inline void SetFoundRoot(LiveObjectSummary* summary) {
1766  summary->set_found_root();
1767}
1768
1769
1770inline void SetFoundWeakRoot(LiveObjectSummary* summary) {
1771  summary->set_found_weak_root();
1772}
1773
1774
1775int LiveObjectList::GetRetainers(Handle<HeapObject> target,
1776                                 Handle<JSObject> instance_filter,
1777                                 Handle<FixedArray> retainers_arr,
1778                                 int start,
1779                                 int dump_limit,
1780                                 int* total_count,
1781                                 LolFilter* filter,
1782                                 LiveObjectSummary* summary,
1783                                 JSFunction* arguments_function,
1784                                 Handle<Object> error) {
1785  HandleScope scope;
1786
1787  // Scratch handles.
1788  Handle<JSObject> detail;
1789  Handle<String> desc;
1790  Handle<HeapObject> retainer;
1791
1792  Isolate* isolate = Isolate::Current();
1793  Factory* factory = isolate->factory();
1794
1795  // Prefetch some needed symbols.
1796  Handle<String> id_sym = factory->LookupAsciiSymbol("id");
1797  Handle<String> desc_sym = factory->LookupAsciiSymbol("desc");
1798  Handle<String> size_sym = factory->LookupAsciiSymbol("size");
1799
1800  NoHandleAllocation ha;
1801  int count = 0;
1802  int index = 0;
1803  Handle<JSObject> last_obj;
1804
1805  *total_count = 0;
1806
1807  // Iterate roots.
1808  LolVisitor lol_visitor(*target, target);
1809  isolate->heap()->IterateStrongRoots(&lol_visitor, VISIT_ALL);
1810  if (!AddRootRetainerIfFound(lol_visitor,
1811                              filter,
1812                              summary,
1813                              SetFoundRoot,
1814                              start,
1815                              dump_limit,
1816                              total_count,
1817                              retainers_arr,
1818                              &count,
1819                              &index,
1820                              "<root>",
1821                              id_sym,
1822                              desc_sym,
1823                              size_sym,
1824                              error)) {
1825    return -1;
1826  }
1827
1828  lol_visitor.reset();
1829  isolate->heap()->IterateWeakRoots(&lol_visitor, VISIT_ALL);
1830  if (!AddRootRetainerIfFound(lol_visitor,
1831                              filter,
1832                              summary,
1833                              SetFoundWeakRoot,
1834                              start,
1835                              dump_limit,
1836                              total_count,
1837                              retainers_arr,
1838                              &count,
1839                              &index,
1840                              "<weak root>",
1841                              id_sym,
1842                              desc_sym,
1843                              size_sym,
1844                              error)) {
1845    return -1;
1846  }
1847
1848  // Iterate the live object lists.
1849  LolIterator it(NULL, last());
1850  for (it.Init(); !it.Done() && (index < dump_limit); it.Next()) {
1851    HeapObject* heap_obj = it.Obj();
1852
1853    // Only look at all JSObjects.
1854    if (heap_obj->IsJSObject()) {
1855      // Skip context extension objects and argument arrays as these are
1856      // checked in the context of functions using them.
1857      JSObject* obj = JSObject::cast(heap_obj);
1858      if (obj->IsJSContextExtensionObject() ||
1859          obj->map()->constructor() == arguments_function) {
1860        continue;
1861      }
1862
1863      // Check if the JS object has a reference to the object looked for.
1864      if (obj->ReferencesObject(*target)) {
1865        // Check instance filter if supplied. This is normally used to avoid
1866        // references from mirror objects (see Runtime_IsInPrototypeChain).
1867        if (!instance_filter->IsUndefined()) {
1868          Object* V = obj;
1869          while (true) {
1870            Object* prototype = V->GetPrototype();
1871            if (prototype->IsNull()) {
1872              break;
1873            }
1874            if (*instance_filter == prototype) {
1875              obj = NULL;  // Don't add this object.
1876              break;
1877            }
1878            V = prototype;
1879          }
1880        }
1881
1882        if (obj != NULL) {
1883          // Skip objects that have been filtered out.
1884          if (filter->Matches(heap_obj)) {
1885            continue;
1886          }
1887
1888          // Valid reference found add to instance array if supplied an update
1889          // count.
1890          last_obj = Handle<JSObject>(obj);
1891          (*total_count)++;
1892
1893          if (summary != NULL) {
1894            summary->Add(heap_obj);
1895          } else if ((*total_count > start) && (index < dump_limit)) {
1896            count++;
1897            if (!retainers_arr.is_null()) {
1898              retainer = Handle<HeapObject>(heap_obj);
1899              bool success = AddObjDetail(retainers_arr,
1900                                          index++,
1901                                          it.Id(),
1902                                          retainer,
1903                                          NULL,
1904                                          id_sym,
1905                                          desc_sym,
1906                                          size_sym,
1907                                          detail,
1908                                          desc,
1909                                          error);
1910              if (!success) return -1;
1911            }
1912          }
1913        }
1914      }
1915    }
1916  }
1917
1918  // Check for circular reference only. This can happen when the object is only
1919  // referenced from mirrors and has a circular reference in which case the
1920  // object is not really alive and would have been garbage collected if not
1921  // referenced from the mirror.
1922
1923  if (*total_count == 1 && !last_obj.is_null() && *last_obj == *target) {
1924    count = 0;
1925    *total_count = 0;
1926  }
1927
1928  return count;
1929}
1930
1931
1932MaybeObject* LiveObjectList::GetObjRetainers(int obj_id,
1933                                             Handle<JSObject> instance_filter,
1934                                             bool verbose,
1935                                             int start,
1936                                             int dump_limit,
1937                                             Handle<JSObject> filter_obj) {
1938  Isolate* isolate = Isolate::Current();
1939  Factory* factory = isolate->factory();
1940  Heap* heap = isolate->heap();
1941
1942  HandleScope scope(isolate);
1943
1944  // Get the target object.
1945  HeapObject* heap_obj = HeapObject::cast(GetObj(obj_id));
1946  if (heap_obj == heap->undefined_value()) {
1947    return heap_obj;
1948  }
1949
1950  Handle<HeapObject> target = Handle<HeapObject>(heap_obj);
1951
1952  // Get the constructor function for context extension and arguments array.
1953  JSObject* arguments_boilerplate =
1954      isolate->context()->global_context()->arguments_boilerplate();
1955  JSFunction* arguments_function =
1956      JSFunction::cast(arguments_boilerplate->map()->constructor());
1957
1958  Handle<JSFunction> args_function = Handle<JSFunction>(arguments_function);
1959  LolFilter filter(filter_obj);
1960
1961  if (!verbose) {
1962    RetainersSummaryWriter writer(target, instance_filter, args_function);
1963    return SummarizePrivate(&writer, &filter, true);
1964
1965  } else {
1966    RetainersDumpWriter writer(target, instance_filter, args_function);
1967    Object* body_obj;
1968    MaybeObject* maybe_result =
1969        DumpPrivate(&writer, start, dump_limit, &filter);
1970    if (!maybe_result->ToObject(&body_obj)) {
1971      return maybe_result;
1972    }
1973
1974    // Set body.id.
1975    Handle<JSObject> body = Handle<JSObject>(JSObject::cast(body_obj));
1976    Handle<String> id_sym = factory->LookupAsciiSymbol("id");
1977    maybe_result = body->SetProperty(*id_sym,
1978                                     Smi::FromInt(obj_id),
1979                                     NONE,
1980                                     kNonStrictMode);
1981    if (maybe_result->IsFailure()) return maybe_result;
1982
1983    return *body;
1984  }
1985}
1986
1987
1988Object* LiveObjectList::PrintObj(int obj_id) {
1989  Object* obj = GetObj(obj_id);
1990  if (!obj) {
1991    return HEAP->undefined_value();
1992  }
1993
1994  EmbeddedVector<char, 128> temp_filename;
1995  static int temp_count = 0;
1996  const char* path_prefix = ".";
1997
1998  Isolate* isolate = Isolate::Current();
1999  Factory* factory = isolate->factory();
2000  Heap* heap = isolate->heap();
2001
2002  if (FLAG_lol_workdir) {
2003    path_prefix = FLAG_lol_workdir;
2004  }
2005  OS::SNPrintF(temp_filename, "%s/lol-print-%d", path_prefix, ++temp_count);
2006
2007  FILE* f = OS::FOpen(temp_filename.start(), "w+");
2008
2009  PrintF(f, "@%d ", LiveObjectList::GetObjId(obj));
2010#ifdef OBJECT_PRINT
2011#ifdef INSPECTOR
2012  Inspector::DumpObjectType(f, obj);
2013#endif  // INSPECTOR
2014  PrintF(f, "\n");
2015  obj->Print(f);
2016#else  // !OBJECT_PRINT
2017  obj->ShortPrint(f);
2018#endif  // !OBJECT_PRINT
2019  PrintF(f, "\n");
2020  Flush(f);
2021  fclose(f);
2022
2023  // Create a string from the temp_file.
2024  // Note: the mmapped resource will take care of closing the file.
2025  MemoryMappedExternalResource* resource =
2026      new MemoryMappedExternalResource(temp_filename.start(), true);
2027  if (resource->exists() && !resource->is_empty()) {
2028    ASSERT(resource->IsAscii());
2029    Handle<String> dump_string =
2030        factory->NewExternalStringFromAscii(resource);
2031    heap->external_string_table()->AddString(*dump_string);
2032    return *dump_string;
2033  } else {
2034    delete resource;
2035  }
2036  return HEAP->undefined_value();
2037}
2038
2039
2040class LolPathTracer: public PathTracer {
2041 public:
2042  LolPathTracer(FILE* out,
2043                Object* search_target,
2044                WhatToFind what_to_find)
2045      : PathTracer(search_target, what_to_find, VISIT_ONLY_STRONG), out_(out) {}
2046
2047 private:
2048  void ProcessResults();
2049
2050  FILE* out_;
2051};
2052
2053
2054void LolPathTracer::ProcessResults() {
2055  if (found_target_) {
2056    PrintF(out_, "=====================================\n");
2057    PrintF(out_, "====        Path to object       ====\n");
2058    PrintF(out_, "=====================================\n\n");
2059
2060    ASSERT(!object_stack_.is_empty());
2061    Object* prev = NULL;
2062    for (int i = 0, index = 0; i < object_stack_.length(); i++) {
2063      Object* obj = object_stack_[i];
2064
2065      // Skip this object if it is basically the internals of the
2066      // previous object (which would have dumped its details already).
2067      if (prev && prev->IsJSObject() &&
2068          (obj != search_target_)) {
2069        JSObject* jsobj = JSObject::cast(prev);
2070        if (obj->IsFixedArray() &&
2071            jsobj->properties() == FixedArray::cast(obj)) {
2072          // Skip this one because it would have been printed as the
2073          // properties of the last object already.
2074          continue;
2075        } else if (obj->IsHeapObject() &&
2076                   jsobj->elements() == HeapObject::cast(obj)) {
2077          // Skip this one because it would have been printed as the
2078          // elements of the last object already.
2079          continue;
2080        }
2081      }
2082
2083      // Print a connecting arrow.
2084      if (i > 0) PrintF(out_, "\n     |\n     |\n     V\n\n");
2085
2086      // Print the object index.
2087      PrintF(out_, "[%d] ", ++index);
2088
2089      // Print the LOL object ID:
2090      int id = LiveObjectList::GetObjId(obj);
2091      if (id > 0) PrintF(out_, "@%d ", id);
2092
2093#ifdef OBJECT_PRINT
2094#ifdef INSPECTOR
2095      Inspector::DumpObjectType(out_, obj);
2096#endif  // INSPECTOR
2097      PrintF(out_, "\n");
2098      obj->Print(out_);
2099#else  // !OBJECT_PRINT
2100      obj->ShortPrint(out_);
2101      PrintF(out_, "\n");
2102#endif  // !OBJECT_PRINT
2103      Flush(out_);
2104    }
2105    PrintF(out_, "\n");
2106    PrintF(out_, "=====================================\n\n");
2107    Flush(out_);
2108  }
2109}
2110
2111
2112Object* LiveObjectList::GetPathPrivate(HeapObject* obj1, HeapObject* obj2) {
2113  EmbeddedVector<char, 128> temp_filename;
2114  static int temp_count = 0;
2115  const char* path_prefix = ".";
2116
2117  if (FLAG_lol_workdir) {
2118    path_prefix = FLAG_lol_workdir;
2119  }
2120  OS::SNPrintF(temp_filename, "%s/lol-getpath-%d", path_prefix, ++temp_count);
2121
2122  FILE* f = OS::FOpen(temp_filename.start(), "w+");
2123
2124  Isolate* isolate = Isolate::Current();
2125  Factory* factory = isolate->factory();
2126  Heap* heap = isolate->heap();
2127
2128  // Save the previous verbosity.
2129  bool prev_verbosity = FLAG_use_verbose_printer;
2130  FLAG_use_verbose_printer = false;
2131
2132  // Dump the paths.
2133  {
2134    // The tracer needs to be scoped because its usage asserts no allocation,
2135    // and we need to allocate the result string below.
2136    LolPathTracer tracer(f, obj2, LolPathTracer::FIND_FIRST);
2137
2138    bool found = false;
2139    if (obj1 == NULL) {
2140      // Check for ObjectGroups that references this object.
2141      // TODO(mlam): refactor this to be more modular.
2142      {
2143        List<ObjectGroup*>* groups = isolate->global_handles()->object_groups();
2144        for (int i = 0; i < groups->length(); i++) {
2145          ObjectGroup* group = groups->at(i);
2146          if (group == NULL) continue;
2147
2148          bool found_group = false;
2149          for (size_t j = 0; j < group->length_; j++) {
2150            Object* object = *(group->objects_[j]);
2151            HeapObject* hobj = HeapObject::cast(object);
2152            if (obj2 == hobj) {
2153              found_group = true;
2154              break;
2155            }
2156          }
2157
2158          if (found_group) {
2159            PrintF(f,
2160                   "obj %p is a member of object group %p {\n",
2161                   reinterpret_cast<void*>(obj2),
2162                   reinterpret_cast<void*>(group));
2163            for (size_t j = 0; j < group->length_; j++) {
2164              Object* object = *(group->objects_[j]);
2165              if (!object->IsHeapObject()) continue;
2166
2167              HeapObject* hobj = HeapObject::cast(object);
2168              int id = GetObjId(hobj);
2169              if (id != 0) {
2170                PrintF(f, "  @%d:", id);
2171              } else {
2172                PrintF(f, "  <no id>:");
2173              }
2174
2175              char buffer[512];
2176              GenerateObjectDesc(hobj, buffer, sizeof(buffer));
2177              PrintF(f, " %s", buffer);
2178              if (hobj == obj2) {
2179                PrintF(f, " <===");
2180              }
2181              PrintF(f, "\n");
2182            }
2183            PrintF(f, "}\n");
2184          }
2185        }
2186      }
2187
2188      PrintF(f, "path from roots to obj %p\n", reinterpret_cast<void*>(obj2));
2189      heap->IterateRoots(&tracer, VISIT_ONLY_STRONG);
2190      found = tracer.found();
2191
2192      if (!found) {
2193        PrintF(f, "  No paths found. Checking symbol tables ...\n");
2194        SymbolTable* symbol_table = HEAP->raw_unchecked_symbol_table();
2195        tracer.VisitPointers(reinterpret_cast<Object**>(&symbol_table),
2196                             reinterpret_cast<Object**>(&symbol_table)+1);
2197        found = tracer.found();
2198        if (!found) {
2199          symbol_table->IteratePrefix(&tracer);
2200          found = tracer.found();
2201        }
2202      }
2203
2204      if (!found) {
2205        PrintF(f, "  No paths found. Checking weak roots ...\n");
2206        // Check weak refs next.
2207        isolate->global_handles()->IterateWeakRoots(&tracer);
2208        found = tracer.found();
2209      }
2210
2211    } else {
2212      PrintF(f, "path from obj %p to obj %p:\n",
2213             reinterpret_cast<void*>(obj1), reinterpret_cast<void*>(obj2));
2214      tracer.TracePathFrom(reinterpret_cast<Object**>(&obj1));
2215      found = tracer.found();
2216    }
2217
2218    if (!found) {
2219      PrintF(f, "  No paths found\n\n");
2220    }
2221  }
2222
2223  // Flush and clean up the dumped file.
2224  Flush(f);
2225  fclose(f);
2226
2227  // Restore the previous verbosity.
2228  FLAG_use_verbose_printer = prev_verbosity;
2229
2230  // Create a string from the temp_file.
2231  // Note: the mmapped resource will take care of closing the file.
2232  MemoryMappedExternalResource* resource =
2233      new MemoryMappedExternalResource(temp_filename.start(), true);
2234  if (resource->exists() && !resource->is_empty()) {
2235    ASSERT(resource->IsAscii());
2236    Handle<String> path_string =
2237        factory->NewExternalStringFromAscii(resource);
2238    heap->external_string_table()->AddString(*path_string);
2239    return *path_string;
2240  } else {
2241    delete resource;
2242  }
2243  return heap->undefined_value();
2244}
2245
2246
2247Object* LiveObjectList::GetPath(int obj_id1,
2248                                int obj_id2,
2249                                Handle<JSObject> instance_filter) {
2250  HandleScope scope;
2251
2252  // Get the target object.
2253  HeapObject* obj1 = NULL;
2254  if (obj_id1 != 0) {
2255    obj1 = HeapObject::cast(GetObj(obj_id1));
2256    if (obj1 == HEAP->undefined_value()) {
2257      return obj1;
2258    }
2259  }
2260
2261  HeapObject* obj2 = HeapObject::cast(GetObj(obj_id2));
2262  if (obj2 == HEAP->undefined_value()) {
2263    return obj2;
2264  }
2265
2266  return GetPathPrivate(obj1, obj2);
2267}
2268
2269
2270void LiveObjectList::DoProcessNonLive(HeapObject* obj) {
2271  // We should only be called if we have at least one lol to search.
2272  ASSERT(last() != NULL);
2273  Element* element = last()->Find(obj);
2274  if (element != NULL) {
2275    NullifyNonLivePointer(&element->obj_);
2276  }
2277}
2278
2279
2280void LiveObjectList::IterateElementsPrivate(ObjectVisitor* v) {
2281  LiveObjectList* lol = last();
2282  while (lol != NULL) {
2283    Element* elements = lol->elements_;
2284    int count = lol->obj_count_;
2285    for (int i = 0; i < count; i++) {
2286      HeapObject** p = &elements[i].obj_;
2287      v->VisitPointer(reinterpret_cast<Object** >(p));
2288    }
2289    lol = lol->prev_;
2290  }
2291}
2292
2293
2294// Purpose: Called by GCEpilogue to purge duplicates.  Not to be called by
2295// anyone else.
2296void LiveObjectList::PurgeDuplicates() {
2297  bool is_sorted = false;
2298  LiveObjectList* lol = last();
2299  if (!lol) {
2300    return;  // Nothing to purge.
2301  }
2302
2303  int total_count = lol->TotalObjCount();
2304  if (!total_count) {
2305    return;  // Nothing to purge.
2306  }
2307
2308  Element* elements = NewArray<Element>(total_count);
2309  int count = 0;
2310
2311  // Copy all the object elements into a consecutive array.
2312  while (lol) {
2313    memcpy(&elements[count], lol->elements_, lol->obj_count_ * sizeof(Element));
2314    count += lol->obj_count_;
2315    lol = lol->prev_;
2316  }
2317  qsort(elements, total_count, sizeof(Element),
2318        reinterpret_cast<RawComparer>(CompareElement));
2319
2320  ASSERT(count == total_count);
2321
2322  // Iterate over all objects in the consolidated list and check for dups.
2323  total_count--;
2324  for (int i = 0; i < total_count; ) {
2325    Element* curr = &elements[i];
2326    HeapObject* curr_obj = curr->obj_;
2327    int j = i+1;
2328    bool done = false;
2329
2330    while (!done && (j < total_count)) {
2331      // Process if the element's object is still live after the current GC.
2332      // Non-live objects will be converted to SMIs i.e. not HeapObjects.
2333      if (curr_obj->IsHeapObject()) {
2334        Element* next = &elements[j];
2335        HeapObject* next_obj = next->obj_;
2336        if (next_obj->IsHeapObject()) {
2337          if (curr_obj != next_obj) {
2338            done = true;
2339            continue;  // Live object but no match.  Move on.
2340          }
2341
2342          // NOTE: we've just GCed the LOLs.  Hence, they are no longer sorted.
2343          // Since we detected at least one need to search for entries, we'll
2344          // sort it to enable the use of NullifyMostRecent() below.  We only
2345          // need to sort it once (except for one exception ... see below).
2346          if (!is_sorted) {
2347            SortAll();
2348            is_sorted = true;
2349          }
2350
2351          // We have a match.  Need to nullify the most recent ref to this
2352          // object.  We'll keep the oldest ref:
2353          // Note: we will nullify the element record in the LOL
2354          // database, not in the local sorted copy of the elements.
2355          NullifyMostRecent(curr_obj);
2356        }
2357      }
2358      // Either the object was already marked for purging, or we just marked
2359      // it.  Either way, if there's more than one dup, then we need to check
2360      // the next element for another possible dup against the current as well
2361      // before we move on.  So, here we go.
2362      j++;
2363    }
2364
2365    // We can move on to checking the match on the next element.
2366    i = j;
2367  }
2368
2369  DeleteArray<Element>(elements);
2370}
2371
2372
2373// Purpose: Purges dead objects and resorts the LOLs.
2374void LiveObjectList::GCEpiloguePrivate() {
2375  // Note: During the GC, ConsStrings may be collected and pointers may be
2376  // forwarded to its constituent string.  As a result, we may find dupes of
2377  // objects references in the LOL list.
2378  // Another common way we get dups is that free chunks that have been swept
2379  // in the oldGen heap may be kept as ByteArray objects in a free list.
2380  //
2381  // When we promote live objects from the youngGen, the object may be moved
2382  // to the start of these free chunks.  Since there is no free or move event
2383  // for the free chunks, their addresses will show up 2 times: once for their
2384  // original free ByteArray selves, and once for the newly promoted youngGen
2385  // object.  Hence, we can get a duplicate address in the LOL again.
2386  //
2387  // We need to eliminate these dups because the LOL implementation expects to
2388  // only have at most one unique LOL reference to any object at any time.
2389  PurgeDuplicates();
2390
2391  // After the GC, sweep away all free'd Elements and compact.
2392  LiveObjectList* prev = NULL;
2393  LiveObjectList* next = NULL;
2394
2395  // Iterating from the youngest lol to the oldest lol.
2396  for (LiveObjectList* lol = last(); lol; lol = prev) {
2397    Element* elements = lol->elements_;
2398    prev = lol->prev();  // Save the prev.
2399
2400    // Remove any references to collected objects.
2401    int i = 0;
2402    while (i < lol->obj_count_) {
2403      Element& element = elements[i];
2404      if (!element.obj_->IsHeapObject()) {
2405        // If the HeapObject address was converted into a SMI, then this
2406        // is a dead object.  Copy the last element over this one.
2407        element = elements[lol->obj_count_ - 1];
2408        lol->obj_count_--;
2409        // We've just moved the last element into this index.  We'll revisit
2410        // this index again.  Hence, no need to increment the iterator.
2411      } else {
2412        i++;  // Look at the next element next.
2413      }
2414    }
2415
2416    int new_count = lol->obj_count_;
2417
2418    // Check if there are any more elements to keep after purging the dead ones.
2419    if (new_count == 0) {
2420      DeleteArray<Element>(elements);
2421      lol->elements_ = NULL;
2422      lol->capacity_ = 0;
2423      ASSERT(lol->obj_count_ == 0);
2424
2425      // If the list is also invisible, the clean up the list as well.
2426      if (lol->id_ == 0) {
2427        // Point the next lol's prev to this lol's prev.
2428        if (next) {
2429          next->prev_ = lol->prev_;
2430        } else {
2431          last_ = lol->prev_;
2432        }
2433
2434        // Delete this now empty and invisible lol.
2435        delete lol;
2436
2437        // Don't point the next to this lol since it is now deleted.
2438        // Leave the next pointer pointing to the current lol.
2439        continue;
2440      }
2441
2442    } else {
2443      // If the obj_count_ is less than the capacity and the difference is
2444      // greater than a specified threshold, then we should shrink the list.
2445      int diff = lol->capacity_ - new_count;
2446      const int kMaxUnusedSpace = 64;
2447      if (diff > kMaxUnusedSpace) {  // Threshold for shrinking.
2448        // Shrink the list.
2449        Element* new_elements = NewArray<Element>(new_count);
2450        memcpy(new_elements, elements, new_count * sizeof(Element));
2451
2452        DeleteArray<Element>(elements);
2453        lol->elements_ = new_elements;
2454        lol->capacity_ = new_count;
2455      }
2456      ASSERT(lol->obj_count_ == new_count);
2457
2458      lol->Sort();  // We've moved objects.  Re-sort in case.
2459    }
2460
2461    // Save the next (for the previous link) in case we need it later.
2462    next = lol;
2463  }
2464
2465#ifdef VERIFY_LOL
2466  if (FLAG_verify_lol) {
2467    Verify();
2468  }
2469#endif
2470}
2471
2472
2473#ifdef VERIFY_LOL
2474void LiveObjectList::Verify(bool match_heap_exactly) {
2475  OS::Print("Verifying the LiveObjectList database:\n");
2476
2477  LiveObjectList* lol = last();
2478  if (lol == NULL) {
2479    OS::Print("  No lol database to verify\n");
2480    return;
2481  }
2482
2483  OS::Print("  Preparing the lol database ...\n");
2484  int total_count = lol->TotalObjCount();
2485
2486  Element* elements = NewArray<Element>(total_count);
2487  int count = 0;
2488
2489  // Copy all the object elements into a consecutive array.
2490  OS::Print("  Copying the lol database ...\n");
2491  while (lol != NULL) {
2492    memcpy(&elements[count], lol->elements_, lol->obj_count_ * sizeof(Element));
2493    count += lol->obj_count_;
2494    lol = lol->prev_;
2495  }
2496  qsort(elements, total_count, sizeof(Element),
2497        reinterpret_cast<RawComparer>(CompareElement));
2498
2499  ASSERT(count == total_count);
2500
2501  // Iterate over all objects in the heap and check for:
2502  // 1. object in LOL but not in heap i.e. error.
2503  // 2. object in heap but not in LOL (possibly not an error).  Usually
2504  //    just means that we don't have the a capture of the latest heap.
2505  //    That is unless we did this verify immediately after a capture,
2506  //    and specified match_heap_exactly = true.
2507
2508  int number_of_heap_objects = 0;
2509  int number_of_matches = 0;
2510  int number_not_in_heap = total_count;
2511  int number_not_in_lol = 0;
2512
2513  OS::Print("  Start verify ...\n");
2514  OS::Print("  Verifying ...");
2515  Flush();
2516  HeapIterator iterator;
2517  HeapObject* heap_obj = NULL;
2518  while ((heap_obj = iterator.next()) != NULL) {
2519    number_of_heap_objects++;
2520
2521    // Check if the heap_obj is in the lol.
2522    Element key;
2523    key.obj_ = heap_obj;
2524
2525    Element* result = reinterpret_cast<Element*>(
2526        bsearch(&key, elements, total_count, sizeof(Element),
2527                reinterpret_cast<RawComparer>(CompareElement)));
2528
2529    if (result != NULL) {
2530      number_of_matches++;
2531      number_not_in_heap--;
2532      // Mark it as found by changing it into a SMI (mask off low bit).
2533      // Note: we cannot use HeapObject::cast() here because it asserts that
2534      // the HeapObject bit is set on the address, but we're unsetting it on
2535      // purpose here for our marking.
2536      result->obj_ = reinterpret_cast<HeapObject*>(heap_obj->address());
2537
2538    } else {
2539      number_not_in_lol++;
2540      if (match_heap_exactly) {
2541        OS::Print("heap object %p NOT in lol database\n", heap_obj);
2542      }
2543    }
2544    // Show some sign of life.
2545    if (number_of_heap_objects % 1000 == 0) {
2546      OS::Print(".");
2547      fflush(stdout);
2548    }
2549  }
2550  OS::Print("\n");
2551
2552  // Reporting lol objects not found in the heap.
2553  if (number_not_in_heap) {
2554    int found = 0;
2555    for (int i = 0; (i < total_count) && (found < number_not_in_heap); i++) {
2556      Element& element = elements[i];
2557      if (element.obj_->IsHeapObject()) {
2558        OS::Print("lol database object [%d of %d] %p NOT in heap\n",
2559                  i, total_count, element.obj_);
2560        found++;
2561      }
2562    }
2563  }
2564
2565  DeleteArray<Element>(elements);
2566
2567  OS::Print("number of objects in lol database %d\n", total_count);
2568  OS::Print("number of heap objects .......... %d\n", number_of_heap_objects);
2569  OS::Print("number of matches ............... %d\n", number_of_matches);
2570  OS::Print("number NOT in heap .............. %d\n", number_not_in_heap);
2571  OS::Print("number NOT in lol database ...... %d\n", number_not_in_lol);
2572
2573  if (number_of_matches != total_count) {
2574    OS::Print("  *** ERROR: "
2575              "NOT all lol database objects match heap objects.\n");
2576  }
2577  if (number_not_in_heap != 0) {
2578    OS::Print("  *** ERROR: %d lol database objects not found in heap.\n",
2579              number_not_in_heap);
2580  }
2581  if (match_heap_exactly) {
2582    if (!(number_not_in_lol == 0)) {
2583      OS::Print("  *** ERROR: %d heap objects NOT found in lol database.\n",
2584                number_not_in_lol);
2585    }
2586  }
2587
2588  ASSERT(number_of_matches == total_count);
2589  ASSERT(number_not_in_heap == 0);
2590  ASSERT(number_not_in_lol == (number_of_heap_objects - total_count));
2591  if (match_heap_exactly) {
2592    ASSERT(total_count == number_of_heap_objects);
2593    ASSERT(number_not_in_lol == 0);
2594  }
2595
2596  OS::Print("  Verify the lol database is sorted ...\n");
2597  lol = last();
2598  while (lol != NULL) {
2599    Element* elements = lol->elements_;
2600    for (int i = 0; i < lol->obj_count_ - 1; i++) {
2601      if (elements[i].obj_ >= elements[i+1].obj_) {
2602        OS::Print("  *** ERROR: lol %p obj[%d] %p > obj[%d] %p\n",
2603                  lol, i, elements[i].obj_, i+1, elements[i+1].obj_);
2604      }
2605    }
2606    lol = lol->prev_;
2607  }
2608
2609  OS::Print("  DONE verifying.\n\n\n");
2610}
2611
2612
2613void LiveObjectList::VerifyNotInFromSpace() {
2614  OS::Print("VerifyNotInFromSpace() ...\n");
2615  LolIterator it(NULL, last());
2616  Heap* heap = ISOLATE->heap();
2617  int i = 0;
2618  for (it.Init(); !it.Done(); it.Next()) {
2619    HeapObject* heap_obj = it.Obj();
2620    if (heap->InFromSpace(heap_obj)) {
2621      OS::Print(" ERROR: VerifyNotInFromSpace: [%d] obj %p in From space %p\n",
2622                i++, heap_obj, Heap::new_space()->FromSpaceStart());
2623    }
2624  }
2625}
2626#endif  // VERIFY_LOL
2627
2628
2629} }  // namespace v8::internal
2630
2631#endif  // LIVE_OBJECT_LIST
2632