/*
 * Copyright (C) 2008 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/*
 * Preparation and completion of hprof data generation.  The output is
 * written into two files and then combined.  This is necessary because
 * we generate some of the data (strings and classes) while we dump the
 * heap, and some analysis tools require that the class and string data
 * appear first.
 */

#include "hprof.h"

#include <cutils/open_memstream.h>
#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>
#include <sys/uio.h>
#include <time.h>
#include <time.h>
#include <unistd.h>

#include <set>

#include "class_linker.h"
#include "debugger.h"
#include "file.h"
#include "globals.h"
#include "heap.h"
#include "logging.h"
#include "object.h"
#include "object_utils.h"
#include "safe_map.h"
#include "scoped_heap_lock.h"
#include "stringprintf.h"
#include "thread_list.h"

namespace art {

namespace hprof {

#define UNIQUE_ERROR -((((uintptr_t)__func__) << 16 | __LINE__) & (0x7fffffff))

#define HPROF_TIME 0
#define HPROF_NULL_STACK_TRACE   0
#define HPROF_NULL_THREAD        0

#define U2_TO_BUF_BE(buf, offset, value) \
    do { \
      unsigned char* buf_ = (unsigned char*)(buf); \
      int offset_ = (int)(offset); \
      uint16_t value_ = (uint16_t)(value); \
      buf_[offset_ + 0] = (unsigned char)(value_ >>  8); \
      buf_[offset_ + 1] = (unsigned char)(value_      ); \
    } while (0)

#define U4_TO_BUF_BE(buf, offset, value) \
    do { \
      unsigned char* buf_ = (unsigned char*)(buf); \
      int offset_ = (int)(offset); \
      uint32_t value_ = (uint32_t)(value); \
      buf_[offset_ + 0] = (unsigned char)(value_ >> 24); \
      buf_[offset_ + 1] = (unsigned char)(value_ >> 16); \
      buf_[offset_ + 2] = (unsigned char)(value_ >>  8); \
      buf_[offset_ + 3] = (unsigned char)(value_      ); \
    } while (0)

#define U8_TO_BUF_BE(buf, offset, value) \
    do { \
      unsigned char* buf_ = (unsigned char*)(buf); \
      int offset_ = (int)(offset); \
      uint64_t value_ = (uint64_t)(value); \
      buf_[offset_ + 0] = (unsigned char)(value_ >> 56); \
      buf_[offset_ + 1] = (unsigned char)(value_ >> 48); \
      buf_[offset_ + 2] = (unsigned char)(value_ >> 40); \
      buf_[offset_ + 3] = (unsigned char)(value_ >> 32); \
      buf_[offset_ + 4] = (unsigned char)(value_ >> 24); \
      buf_[offset_ + 5] = (unsigned char)(value_ >> 16); \
      buf_[offset_ + 6] = (unsigned char)(value_ >>  8); \
      buf_[offset_ + 7] = (unsigned char)(value_      ); \
    } while (0)

enum HprofTag {
  HPROF_TAG_STRING = 0x01,
  HPROF_TAG_LOAD_CLASS = 0x02,
  HPROF_TAG_UNLOAD_CLASS = 0x03,
  HPROF_TAG_STACK_FRAME = 0x04,
  HPROF_TAG_STACK_TRACE = 0x05,
  HPROF_TAG_ALLOC_SITES = 0x06,
  HPROF_TAG_HEAP_SUMMARY = 0x07,
  HPROF_TAG_START_THREAD = 0x0A,
  HPROF_TAG_END_THREAD = 0x0B,
  HPROF_TAG_HEAP_DUMP = 0x0C,
  HPROF_TAG_HEAP_DUMP_SEGMENT = 0x1C,
  HPROF_TAG_HEAP_DUMP_END = 0x2C,
  HPROF_TAG_CPU_SAMPLES = 0x0D,
  HPROF_TAG_CONTROL_SETTINGS = 0x0E,
};

// Values for the first byte of HEAP_DUMP and HEAP_DUMP_SEGMENT records:
enum HprofHeapTag {
  // Traditional.
  HPROF_ROOT_UNKNOWN = 0xFF,
  HPROF_ROOT_JNI_GLOBAL = 0x01,
  HPROF_ROOT_JNI_LOCAL = 0x02,
  HPROF_ROOT_JAVA_FRAME = 0x03,
  HPROF_ROOT_NATIVE_STACK = 0x04,
  HPROF_ROOT_STICKY_CLASS = 0x05,
  HPROF_ROOT_THREAD_BLOCK = 0x06,
  HPROF_ROOT_MONITOR_USED = 0x07,
  HPROF_ROOT_THREAD_OBJECT = 0x08,
  HPROF_CLASS_DUMP = 0x20,
  HPROF_INSTANCE_DUMP = 0x21,
  HPROF_OBJECT_ARRAY_DUMP = 0x22,
  HPROF_PRIMITIVE_ARRAY_DUMP = 0x23,

  // Android.
  HPROF_HEAP_DUMP_INFO = 0xfe,
  HPROF_ROOT_INTERNED_STRING = 0x89,
  HPROF_ROOT_FINALIZING = 0x8a,  // Obsolete.
  HPROF_ROOT_DEBUGGER = 0x8b,
  HPROF_ROOT_REFERENCE_CLEANUP = 0x8c,  // Obsolete.
  HPROF_ROOT_VM_INTERNAL = 0x8d,
  HPROF_ROOT_JNI_MONITOR = 0x8e,
  HPROF_UNREACHABLE = 0x90,  // Obsolete.
  HPROF_PRIMITIVE_ARRAY_NODATA_DUMP = 0xc3,
};

enum HprofHeapId {
  HPROF_HEAP_DEFAULT = 0,
  HPROF_HEAP_ZYGOTE = 'Z',
  HPROF_HEAP_APP = 'A'
};

enum HprofBasicType {
  hprof_basic_object = 2,
  hprof_basic_boolean = 4,
  hprof_basic_char = 5,
  hprof_basic_float = 6,
  hprof_basic_double = 7,
  hprof_basic_byte = 8,
  hprof_basic_short = 9,
  hprof_basic_int = 10,
  hprof_basic_long = 11,
};

typedef uint32_t HprofId;
typedef HprofId HprofStringId;
typedef HprofId HprofObjectId;
typedef HprofId HprofClassObjectId;
typedef std::set<const Class*> ClassSet;
typedef std::set<const Class*>::iterator ClassSetIterator;
typedef SafeMap<std::string, size_t> StringMap;
typedef SafeMap<std::string, size_t>::iterator StringMapIterator;

// Represents a top-level hprof record, whose serialized format is:
// U1  TAG: denoting the type of the record
// U4  TIME: number of microseconds since the time stamp in the header
// U4  LENGTH: number of bytes that follow this uint32_t field and belong to this record
// U1* BODY: as many bytes as specified in the above uint32_t field
class HprofRecord {
 public:
  int Flush(FILE* fp) {
    if (dirty_) {
      unsigned char headBuf[sizeof(uint8_t) + 2 * sizeof(uint32_t)];

      headBuf[0] = tag_;
      U4_TO_BUF_BE(headBuf, 1, time_);
      U4_TO_BUF_BE(headBuf, 5, length_);

      int nb = fwrite(headBuf, 1, sizeof(headBuf), fp);
      if (nb != sizeof(headBuf)) {
        return UNIQUE_ERROR;
      }
      nb = fwrite(body_, 1, length_, fp);
      if (nb != (int)length_) {
        return UNIQUE_ERROR;
      }

      dirty_ = false;
    }
    // TODO if we used less than half (or whatever) of allocLen, shrink the buffer.
    return 0;
  }

  int AddU1(uint8_t value) {
    int err = GuaranteeRecordAppend(1);
    if (err != 0) {
      return err;
    }

    body_[length_++] = value;
    return 0;
  }

  int AddU2(uint16_t value) {
    return AddU2List(&value, 1);
  }

  int AddU4(uint32_t value) {
    return AddU4List(&value, 1);
  }

  int AddU8(uint64_t value) {
    return AddU8List(&value, 1);
  }

  int AddId(HprofObjectId value) {
    return AddU4((uint32_t) value);
  }

  int AddU1List(const uint8_t *values, size_t numValues) {
    int err = GuaranteeRecordAppend(numValues);
    if (err != 0) {
      return err;
    }

    memcpy(body_ + length_, values, numValues);
    length_ += numValues;
    return 0;
  }

  int AddU2List(const uint16_t *values, size_t numValues) {
    int err = GuaranteeRecordAppend(numValues * 2);
    if (err != 0) {
      return err;
    }

    unsigned char* insert = body_ + length_;
    for (size_t i = 0; i < numValues; i++) {
      U2_TO_BUF_BE(insert, 0, *values++);
      insert += sizeof(*values);
    }
    length_ += numValues * 2;
    return 0;
  }

  int AddU4List(const uint32_t *values, size_t numValues) {
    int err = GuaranteeRecordAppend(numValues * 4);
    if (err != 0) {
      return err;
    }

    unsigned char* insert = body_ + length_;
    for (size_t i = 0; i < numValues; i++) {
      U4_TO_BUF_BE(insert, 0, *values++);
      insert += sizeof(*values);
    }
    length_ += numValues * 4;
    return 0;
  }

  int AddU8List(const uint64_t *values, size_t numValues) {
    int err = GuaranteeRecordAppend(numValues * 8);
    if (err != 0) {
      return err;
    }

    unsigned char* insert = body_ + length_;
    for (size_t i = 0; i < numValues; i++) {
      U8_TO_BUF_BE(insert, 0, *values++);
      insert += sizeof(*values);
    }
    length_ += numValues * 8;
    return 0;
  }

  int AddIdList(const HprofObjectId *values, size_t numValues) {
    return AddU4List((const uint32_t*) values, numValues);
  }

  int AddUtf8String(const char* str) {
    // The terminating NUL character is NOT written.
    return AddU1List((const uint8_t *)str, strlen(str));
  }

  unsigned char* body_;
  uint32_t time_;
  uint32_t length_;
  size_t alloc_length_;
  uint8_t tag_;
  bool dirty_;

 private:
  int GuaranteeRecordAppend(size_t nmore) {
    size_t minSize = length_ + nmore;
    if (minSize > alloc_length_) {
      size_t newAllocLen = alloc_length_ * 2;
      if (newAllocLen < minSize) {
        newAllocLen = alloc_length_ + nmore + nmore/2;
      }
      unsigned char* newBody = (unsigned char*)realloc(body_, newAllocLen);
      if (newBody != NULL) {
        body_ = newBody;
        alloc_length_ = newAllocLen;
      } else {
        // TODO: set an error flag so future ops will fail
        return UNIQUE_ERROR;
      }
    }

    CHECK_LE(length_ + nmore, alloc_length_);
    return 0;
  }
};

class Hprof {
 public:
  Hprof(const char* output_filename, int fd, bool write_header, bool direct_to_ddms);
  ~Hprof();

  void VisitRoot(const Object* obj);
  int DumpHeapObject(const Object *obj);
  void Finish();

 private:
  int DumpClasses();
  int DumpStrings();
  int StartNewRecord(uint8_t tag, uint32_t time);
  int FlushCurrentRecord();
  int MarkRootObject(const Object *obj, jobject jniObj);
  HprofClassObjectId LookupClassId(const Class* c);
  HprofStringId LookupStringId(String* string);
  HprofStringId LookupStringId(const char* string);
  HprofStringId LookupStringId(const std::string& string);
  HprofStringId LookupClassNameId(const Class* c);

  // current_record_ *must* be first so that we can cast from a context to a record.
  HprofRecord current_record_;

  uint32_t gc_thread_serial_number_;
  uint8_t gc_scan_state_;
  HprofHeapId current_heap_; // which heap we're currently emitting
  size_t objects_in_segment_;

  // If direct_to_ddms_ is set, "file_name_" and "fd" will be ignored.
  // Otherwise, "file_name_" must be valid, though if "fd" >= 0 it will
  // only be used for debug messages.
  bool direct_to_ddms_;
  std::string file_name_;
  char* file_data_ptr_;   // for open_memstream
  size_t file_data_size_; // for open_memstream
  FILE *mem_fp_;
  int fd_;

  ClassSet classes_;
  size_t next_string_id_;
  StringMap strings_;

  DISALLOW_COPY_AND_ASSIGN(Hprof);
};

Hprof::Hprof(const char* output_filename, int fd, bool write_header, bool direct_to_ddms)
    : current_record_(),
      gc_thread_serial_number_(0),
      gc_scan_state_(0),
      current_heap_(HPROF_HEAP_DEFAULT),
      objects_in_segment_(0),
      direct_to_ddms_(0),
      file_name_(output_filename),
      file_data_ptr_(NULL),
      file_data_size_(0),
      mem_fp_(NULL),
      fd_(0),
      next_string_id_(0x400000) {

  LOG(INFO) << "hprof: heap dump starting (\"" << output_filename << "\", fd=" << fd
            << ", write_header=" << write_header << ", direct_to_ddms=" << direct_to_ddms << ")";

  // Have to do this here, because it must happen after we
  // memset the struct (want to treat file_data_ptr_/file_data_size_
  // as read-only while the file is open).
  FILE *fp = open_memstream(&file_data_ptr_, &file_data_size_);
  if (fp == NULL) {
    // not expected
    PLOG(FATAL) << "open_memstream failed";
  }

  direct_to_ddms_ = direct_to_ddms;
  mem_fp_ = fp;
  fd_ = fd;

  current_record_.alloc_length_ = 128;
  current_record_.body_ = (unsigned char*)malloc(current_record_.alloc_length_);
  // TODO check for/return an error

  if (write_header) {
    char magic[] = "JAVA PROFILE 1.0.3";
    unsigned char buf[4];

    // Write the file header.
    // U1: NUL-terminated magic string.
    fwrite(magic, 1, sizeof(magic), fp);

    // U4: size of identifiers.  We're using addresses as IDs, so make sure a pointer fits.
    U4_TO_BUF_BE(buf, 0, sizeof(void *));
    fwrite(buf, 1, sizeof(uint32_t), fp);

    // The current time, in milliseconds since 0:00 GMT, 1/1/70.
    timeval now;
    uint64_t nowMs;
    if (gettimeofday(&now, NULL) < 0) {
      nowMs = 0;
    } else {
      nowMs = (uint64_t)now.tv_sec * 1000 + now.tv_usec / 1000;
    }

    // U4: high word of the 64-bit time.
    U4_TO_BUF_BE(buf, 0, (uint32_t)(nowMs >> 32));
    fwrite(buf, 1, sizeof(uint32_t), fp);

    // U4: low word of the 64-bit time.
    U4_TO_BUF_BE(buf, 0, (uint32_t)(nowMs & 0xffffffffULL));
    fwrite(buf, 1, sizeof(uint32_t), fp); //xxx fix the time
  }
}

int Hprof::StartNewRecord(uint8_t tag, uint32_t time) {
  HprofRecord *rec = &current_record_;

  int err = rec->Flush(mem_fp_);
  if (err != 0) {
    return err;
  } else if (rec->dirty_) {
    return UNIQUE_ERROR;
  }

  rec->dirty_ = true;
  rec->tag_ = tag;
  rec->time_ = time;
  rec->length_ = 0;
  return 0;
}

int Hprof::FlushCurrentRecord() {
  return current_record_.Flush(mem_fp_);
}

// Set DUMP_PRIM_DATA to 1 if you want to include the contents
// of primitive arrays (byte arrays, character arrays, etc.)
// in heap dumps.  This can be a large amount of data.
#define DUMP_PRIM_DATA 1

#define OBJECTS_PER_SEGMENT     ((size_t)128)
#define BYTES_PER_SEGMENT       ((size_t)4096)

// The static field-name for the synthetic object generated to account
// for class static overhead.
#define STATIC_OVERHEAD_NAME    "$staticOverhead"
// The ID for the synthetic object generated to account for class static overhead.
#define CLASS_STATICS_ID(c) ((HprofObjectId)(((uint32_t)(c)) | 1))

static HprofBasicType SignatureToBasicTypeAndSize(const char* sig, size_t* sizeOut) {
  char c = sig[0];
  HprofBasicType ret;
  size_t size;

  switch (c) {
  case '[':
  case 'L': ret = hprof_basic_object;  size = 4; break;
  case 'Z': ret = hprof_basic_boolean; size = 1; break;
  case 'C': ret = hprof_basic_char;    size = 2; break;
  case 'F': ret = hprof_basic_float;   size = 4; break;
  case 'D': ret = hprof_basic_double;  size = 8; break;
  case 'B': ret = hprof_basic_byte;    size = 1; break;
  case 'S': ret = hprof_basic_short;   size = 2; break;
  default: CHECK(false);
  case 'I': ret = hprof_basic_int;     size = 4; break;
  case 'J': ret = hprof_basic_long;    size = 8; break;
  }

  if (sizeOut != NULL) {
    *sizeOut = size;
  }

  return ret;
}

static HprofBasicType PrimitiveToBasicTypeAndSize(Primitive::Type prim, size_t *sizeOut) {
  HprofBasicType ret;
  size_t size;

  switch (prim) {
  case Primitive::kPrimBoolean: ret = hprof_basic_boolean; size = 1; break;
  case Primitive::kPrimChar:    ret = hprof_basic_char;    size = 2; break;
  case Primitive::kPrimFloat:   ret = hprof_basic_float;   size = 4; break;
  case Primitive::kPrimDouble:  ret = hprof_basic_double;  size = 8; break;
  case Primitive::kPrimByte:    ret = hprof_basic_byte;    size = 1; break;
  case Primitive::kPrimShort:   ret = hprof_basic_short;   size = 2; break;
  default: CHECK(false);
  case Primitive::kPrimInt:     ret = hprof_basic_int;     size = 4; break;
  case Primitive::kPrimLong:    ret = hprof_basic_long;    size = 8; break;
  }

  if (sizeOut != NULL) {
    *sizeOut = size;
  }

  return ret;
}

// Always called when marking objects, but only does
// something when ctx->gc_scan_state_ is non-zero, which is usually
// only true when marking the root set or unreachable
// objects.  Used to add rootset references to obj.
int Hprof::MarkRootObject(const Object *obj, jobject jniObj) {
  HprofRecord* rec = &current_record_;
  HprofHeapTag heapTag = (HprofHeapTag)gc_scan_state_;

  if (heapTag == 0) {
    return 0;
  }

  if (objects_in_segment_ >= OBJECTS_PER_SEGMENT || rec->length_ >= BYTES_PER_SEGMENT) {
    // This flushes the old segment and starts a new one.
    StartNewRecord(HPROF_TAG_HEAP_DUMP_SEGMENT, HPROF_TIME);
    objects_in_segment_ = 0;
  }

  switch (heapTag) {
  // ID: object ID
  case HPROF_ROOT_UNKNOWN:
  case HPROF_ROOT_STICKY_CLASS:
  case HPROF_ROOT_MONITOR_USED:
  case HPROF_ROOT_INTERNED_STRING:
  case HPROF_ROOT_DEBUGGER:
  case HPROF_ROOT_VM_INTERNAL:
    rec->AddU1(heapTag);
    rec->AddId((HprofObjectId)obj);
    break;

  // ID: object ID
  // ID: JNI global ref ID
  case HPROF_ROOT_JNI_GLOBAL:
    rec->AddU1(heapTag);
    rec->AddId((HprofObjectId)obj);
    rec->AddId((HprofId)jniObj);
    break;

  // ID: object ID
  // U4: thread serial number
  // U4: frame number in stack trace (-1 for empty)
  case HPROF_ROOT_JNI_LOCAL:
  case HPROF_ROOT_JNI_MONITOR:
  case HPROF_ROOT_JAVA_FRAME:
    rec->AddU1(heapTag);
    rec->AddId((HprofObjectId)obj);
    rec->AddU4(gc_thread_serial_number_);
    rec->AddU4((uint32_t)-1);
    break;

  // ID: object ID
  // U4: thread serial number
  case HPROF_ROOT_NATIVE_STACK:
  case HPROF_ROOT_THREAD_BLOCK:
    rec->AddU1(heapTag);
    rec->AddId((HprofObjectId)obj);
    rec->AddU4(gc_thread_serial_number_);
    break;

  // ID: thread object ID
  // U4: thread serial number
  // U4: stack trace serial number
  case HPROF_ROOT_THREAD_OBJECT:
    rec->AddU1(heapTag);
    rec->AddId((HprofObjectId)obj);
    rec->AddU4(gc_thread_serial_number_);
    rec->AddU4((uint32_t)-1);    //xxx
    break;

  case HPROF_CLASS_DUMP:
  case HPROF_INSTANCE_DUMP:
  case HPROF_OBJECT_ARRAY_DUMP:
  case HPROF_PRIMITIVE_ARRAY_DUMP:
  case HPROF_HEAP_DUMP_INFO:
  case HPROF_PRIMITIVE_ARRAY_NODATA_DUMP:
    // Ignored.
    break;

  case HPROF_ROOT_FINALIZING:
  case HPROF_ROOT_REFERENCE_CLEANUP:
  case HPROF_UNREACHABLE:
    LOG(FATAL) << "obsolete tag " << static_cast<int>(heapTag);
    break;
  }

  objects_in_segment_++;
  return 0;
}

static int StackTraceSerialNumber(const void* /*obj*/) {
  return HPROF_NULL_STACK_TRACE;
}

int Hprof::DumpHeapObject(const Object* obj) {
  HprofRecord *rec = &current_record_;
  HprofHeapId desiredHeap = false ? HPROF_HEAP_ZYGOTE : HPROF_HEAP_APP; // TODO: zygote objects?

  if (objects_in_segment_ >= OBJECTS_PER_SEGMENT || rec->length_ >= BYTES_PER_SEGMENT) {
    // This flushes the old segment and starts a new one.
    StartNewRecord(HPROF_TAG_HEAP_DUMP_SEGMENT, HPROF_TIME);
    objects_in_segment_ = 0;

    // Starting a new HEAP_DUMP resets the heap to default.
    current_heap_ = HPROF_HEAP_DEFAULT;
  }

  if (desiredHeap != current_heap_) {
    HprofStringId nameId;

    // This object is in a different heap than the current one.
    // Emit a HEAP_DUMP_INFO tag to change heaps.
    rec->AddU1(HPROF_HEAP_DUMP_INFO);
    rec->AddU4((uint32_t)desiredHeap);   // uint32_t: heap id
    switch (desiredHeap) {
    case HPROF_HEAP_APP:
      nameId = LookupStringId("app");
      break;
    case HPROF_HEAP_ZYGOTE:
      nameId = LookupStringId("zygote");
      break;
    default:
      // Internal error
      LOG(ERROR) << "Unexpected desiredHeap";
      nameId = LookupStringId("<ILLEGAL>");
      break;
    }
    rec->AddId(nameId);
    current_heap_ = desiredHeap;
  }

  Class* c = obj->GetClass();
  if (c == NULL) {
    // This object will bother HprofReader, because it has a NULL
    // class, so just don't dump it. It could be
    // gDvm.unlinkedJavaLangClass or it could be an object just
    // allocated which hasn't been initialized yet.
  } else {
    if (obj->IsClass()) {
      const Class* thisClass = obj->AsClass();
      // obj is a ClassObject.
      size_t sFieldCount = thisClass->NumStaticFields();
      if (sFieldCount != 0) {
        int byteLength = sFieldCount*sizeof(JValue); // TODO bogus; fields are packed
        // Create a byte array to reflect the allocation of the
        // StaticField array at the end of this class.
        rec->AddU1(HPROF_PRIMITIVE_ARRAY_DUMP);
        rec->AddId(CLASS_STATICS_ID(obj));
        rec->AddU4(StackTraceSerialNumber(obj));
        rec->AddU4(byteLength);
        rec->AddU1(hprof_basic_byte);
        for (int i = 0; i < byteLength; i++) {
          rec->AddU1(0);
        }
      }

      rec->AddU1(HPROF_CLASS_DUMP);
      rec->AddId(LookupClassId(thisClass));
      rec->AddU4(StackTraceSerialNumber(thisClass));
      rec->AddId(LookupClassId(thisClass->GetSuperClass()));
      rec->AddId((HprofObjectId)thisClass->GetClassLoader());
      rec->AddId((HprofObjectId)0);    // no signer
      rec->AddId((HprofObjectId)0);    // no prot domain
      rec->AddId((HprofId)0);           // reserved
      rec->AddId((HprofId)0);           // reserved
      if (thisClass->IsClassClass()) {
        // ClassObjects have their static fields appended, so aren't all the same size.
        // But they're at least this size.
        rec->AddU4(sizeof(Class)); // instance size
      } else if (thisClass->IsArrayClass() || thisClass->IsPrimitive()) {
        rec->AddU4(0);
      } else {
        rec->AddU4(thisClass->GetObjectSize()); // instance size
      }

      rec->AddU2(0); // empty const pool

      FieldHelper fh;

      // Static fields
      if (sFieldCount == 0) {
        rec->AddU2((uint16_t)0);
      } else {
        rec->AddU2((uint16_t)(sFieldCount+1));
        rec->AddId(LookupStringId(STATIC_OVERHEAD_NAME));
        rec->AddU1(hprof_basic_object);
        rec->AddId(CLASS_STATICS_ID(obj));

        for (size_t i = 0; i < sFieldCount; ++i) {
          Field* f = thisClass->GetStaticField(i);
          fh.ChangeField(f);

          size_t size;
          HprofBasicType t = SignatureToBasicTypeAndSize(fh.GetTypeDescriptor(), &size);
          rec->AddId(LookupStringId(fh.GetName()));
          rec->AddU1(t);
          if (size == 1) {
            rec->AddU1(static_cast<uint8_t>(f->Get32(NULL)));
          } else if (size == 2) {
            rec->AddU2(static_cast<uint16_t>(f->Get32(NULL)));
          } else if (size == 4) {
            rec->AddU4(f->Get32(NULL));
          } else if (size == 8) {
            rec->AddU8(f->Get64(NULL));
          } else {
            CHECK(false);
          }
        }
      }

      // Instance fields for this class (no superclass fields)
      int iFieldCount = thisClass->IsObjectClass() ? 0 : thisClass->NumInstanceFields();
      rec->AddU2((uint16_t)iFieldCount);
      for (int i = 0; i < iFieldCount; ++i) {
        Field* f = thisClass->GetInstanceField(i);
        fh.ChangeField(f);
        HprofBasicType t = SignatureToBasicTypeAndSize(fh.GetTypeDescriptor(), NULL);
        rec->AddId(LookupStringId(fh.GetName()));
        rec->AddU1(t);
      }
    } else if (c->IsArrayClass()) {
      const Array* aobj = obj->AsArray();
      uint32_t length = aobj->GetLength();

      if (obj->IsObjectArray()) {
        // obj is an object array.
        rec->AddU1(HPROF_OBJECT_ARRAY_DUMP);

        rec->AddId((HprofObjectId)obj);
        rec->AddU4(StackTraceSerialNumber(obj));
        rec->AddU4(length);
        rec->AddId(LookupClassId(c));

        // Dump the elements, which are always objects or NULL.
        rec->AddIdList((const HprofObjectId *)aobj->GetRawData(sizeof(Object*)), length);
      } else {
        size_t size;
        HprofBasicType t = PrimitiveToBasicTypeAndSize(c->GetComponentType()->GetPrimitiveType(), &size);

        // obj is a primitive array.
#if DUMP_PRIM_DATA
        rec->AddU1(HPROF_PRIMITIVE_ARRAY_DUMP);
#else
        rec->AddU1(HPROF_PRIMITIVE_ARRAY_NODATA_DUMP);
#endif

        rec->AddId((HprofObjectId)obj);
        rec->AddU4(StackTraceSerialNumber(obj));
        rec->AddU4(length);
        rec->AddU1(t);

#if DUMP_PRIM_DATA
        // Dump the raw, packed element values.
        if (size == 1) {
          rec->AddU1List((const uint8_t *)aobj->GetRawData(sizeof(uint8_t)), length);
        } else if (size == 2) {
          rec->AddU2List((const uint16_t *)(void *)aobj->GetRawData(sizeof(uint16_t)), length);
        } else if (size == 4) {
          rec->AddU4List((const uint32_t *)(void *)aobj->GetRawData(sizeof(uint32_t)), length);
        } else if (size == 8) {
          rec->AddU8List((const uint64_t *)aobj->GetRawData(sizeof(uint64_t)), length);
        }
#endif
      }
    } else {
      // obj is an instance object.
      rec->AddU1(HPROF_INSTANCE_DUMP);
      rec->AddId((HprofObjectId)obj);
      rec->AddU4(StackTraceSerialNumber(obj));
      rec->AddId(LookupClassId(c));

      // Reserve some space for the length of the instance data, which we won't
      // know until we're done writing it.
      size_t sizePatchOffset = rec->length_;
      rec->AddU4(0x77777777);

      // Write the instance data;  fields for this class, followed by super class fields,
      // and so on. Don't write the klass or monitor fields of Object.class.
      const Class* sclass = c;
      FieldHelper fh;
      while (!sclass->IsObjectClass()) {
        int ifieldCount = sclass->NumInstanceFields();
        for (int i = 0; i < ifieldCount; i++) {
          Field* f = sclass->GetInstanceField(i);
          fh.ChangeField(f);
          size_t size;
          SignatureToBasicTypeAndSize(fh.GetTypeDescriptor(), &size);
          if (size == 1) {
            rec->AddU1(f->Get32(obj));
          } else if (size == 2) {
            rec->AddU2(f->Get32(obj));
          } else if (size == 4) {
            rec->AddU4(f->Get32(obj));
          } else if (size == 8) {
            rec->AddU8(f->Get64(obj));
          } else {
            CHECK(false);
          }
        }

        sclass = sclass->GetSuperClass();
      }

      // Patch the instance field length.
      size_t savedLen = rec->length_;
      rec->length_ = sizePatchOffset;
      rec->AddU4(savedLen - (sizePatchOffset + 4));
      rec->length_ = savedLen;
    }
  }

  objects_in_segment_++;
  return 0;
}

#define kHeadSuffix "-hptemp"

// TODO: use File::WriteFully
int sysWriteFully(int fd, const void* buf, size_t count, const char* logMsg) {
  while (count != 0) {
    ssize_t actual = TEMP_FAILURE_RETRY(write(fd, buf, count));
    if (actual < 0) {
      int err = errno;
      PLOG(ERROR) << StringPrintf("%s: write failed", logMsg);
      return err;
    } else if (actual != (ssize_t) count) {
      LOG(DEBUG) << StringPrintf("%s: partial write (will retry): (%d of %zd)",
          logMsg, (int) actual, count);
      buf = (const void*) (((const uint8_t*) buf) + actual);
    }
    count -= actual;
  }
  return 0;
}

void Hprof::Finish() {
  // flush the "tail" portion of the output
  StartNewRecord(HPROF_TAG_HEAP_DUMP_END, HPROF_TIME);
  FlushCurrentRecord();

  // create a new Hprof for the start of the file (as opposed to this, which is the tail)
  Hprof headCtx(file_name_.c_str(), fd_, true, direct_to_ddms_);
  headCtx.classes_ = classes_;
  headCtx.strings_ = strings_;

  headCtx.DumpStrings();
  headCtx.DumpClasses();

  // write a dummy stack trace record so the analysis tools don't freak out
  headCtx.StartNewRecord(HPROF_TAG_STACK_TRACE, HPROF_TIME);
  headCtx.current_record_.AddU4(HPROF_NULL_STACK_TRACE);
  headCtx.current_record_.AddU4(HPROF_NULL_THREAD);
  headCtx.current_record_.AddU4(0);    // no frames

  headCtx.FlushCurrentRecord();

  // flush to ensure memstream pointer and size are updated
  fflush(headCtx.mem_fp_);
  fflush(mem_fp_);

  if (direct_to_ddms_) {
    // send the data off to DDMS
    iovec iov[2];
    iov[0].iov_base = headCtx.file_data_ptr_;
    iov[0].iov_len = headCtx.file_data_size_;
    iov[1].iov_base = file_data_ptr_;
    iov[1].iov_len = file_data_size_;
    Dbg::DdmSendChunkV(CHUNK_TYPE("HPDS"), iov, 2);
  } else {
    // open the output file, and copy the head and tail to it.
    CHECK_EQ(headCtx.fd_, fd_);

    int outFd;
    if (headCtx.fd_ >= 0) {
      outFd = dup(headCtx.fd_);
      if (outFd < 0) {
        Thread::Current()->ThrowNewExceptionF("Ljava/lang/RuntimeException;", "Couldn't dump heap; dup(%d) failed: %s", headCtx.fd_, strerror(errno));
        return;
      }
    } else {
      outFd = open(file_name_.c_str(), O_WRONLY|O_CREAT|O_TRUNC, 0644);
      if (outFd < 0) {
        Thread::Current()->ThrowNewExceptionF("Ljava/lang/RuntimeException;", "Couldn't dump heap; open(\"%s\") failed: %s", headCtx.file_name_.c_str(), strerror(errno));
        return;
      }
    }

    // TODO: just use writev(2)?
    int result = sysWriteFully(outFd, headCtx.file_data_ptr_, headCtx.file_data_size_, "hprof-head");
    result |= sysWriteFully(outFd, file_data_ptr_, file_data_size_, "hprof-tail");
    close(outFd);
    if (result != 0) {
      // TODO: better detail message.
      Thread::Current()->ThrowNewExceptionF("Ljava/lang/RuntimeException;", "Couldn't dump heap; check log output for details");
      return;
    }
  }

  // throw out a log message for the benefit of "runhat"
  LOG(INFO) << "hprof: heap dump completed (" << PrettySize(headCtx.file_data_size_ + file_data_size_ + 1023) << ")";
}

Hprof::~Hprof() {
  // we don't own ctx->fd_, do not close
  if (mem_fp_ != NULL) {
    fclose(mem_fp_);
  }
  free(current_record_.body_);
  free(file_data_ptr_);
}

void Hprof::VisitRoot(const Object* obj) {
  uint32_t threadId = 0;  // TODO
  /*RootType */ size_t type = 0; // TODO

  static const HprofHeapTag xlate[] = {
    HPROF_ROOT_UNKNOWN,
    HPROF_ROOT_JNI_GLOBAL,
    HPROF_ROOT_JNI_LOCAL,
    HPROF_ROOT_JAVA_FRAME,
    HPROF_ROOT_NATIVE_STACK,
    HPROF_ROOT_STICKY_CLASS,
    HPROF_ROOT_THREAD_BLOCK,
    HPROF_ROOT_MONITOR_USED,
    HPROF_ROOT_THREAD_OBJECT,
    HPROF_ROOT_INTERNED_STRING,
    HPROF_ROOT_FINALIZING,
    HPROF_ROOT_DEBUGGER,
    HPROF_ROOT_REFERENCE_CLEANUP,
    HPROF_ROOT_VM_INTERNAL,
    HPROF_ROOT_JNI_MONITOR,
  };

  CHECK_LT(type, sizeof(xlate) / sizeof(HprofHeapTag));
  if (obj == NULL) {
    return;
  }
  gc_scan_state_ = xlate[type];
  gc_thread_serial_number_ = threadId;
  MarkRootObject(obj, 0);
  gc_scan_state_ = 0;
  gc_thread_serial_number_ = 0;
}

HprofStringId Hprof::LookupStringId(String* string) {
  return LookupStringId(string->ToModifiedUtf8());
}

HprofStringId Hprof::LookupStringId(const char* string) {
  return LookupStringId(std::string(string));
}

HprofStringId Hprof::LookupStringId(const std::string& string) {
  StringMapIterator it = strings_.find(string);
  if (it != strings_.end()) {
    return it->second;
  }
  HprofStringId id = next_string_id_++;
  strings_.Put(string, id);
  return id;
}

int Hprof::DumpStrings() {
  HprofRecord *rec = &current_record_;

  for (StringMapIterator it = strings_.begin(); it != strings_.end(); ++it) {
    std::string string((*it).first);
    size_t id = (*it).second;

    int err = StartNewRecord(HPROF_TAG_STRING, HPROF_TIME);
    if (err != 0) {
      return err;
    }

    // STRING format:
    // ID:  ID for this string
    // U1*: UTF8 characters for string (NOT NULL terminated)
    //      (the record format encodes the length)
    err = rec->AddU4(id);
    if (err != 0) {
      return err;
    }
    err = rec->AddUtf8String(string.c_str());
    if (err != 0) {
      return err;
    }
  }

  return 0;
}

HprofStringId Hprof::LookupClassNameId(const Class* c) {
  return LookupStringId(PrettyDescriptor(c));
}

HprofClassObjectId Hprof::LookupClassId(const Class* c) {
  if (c == NULL) {
    // c is the superclass of java.lang.Object or a primitive
    return (HprofClassObjectId)0;
  }

  std::pair<ClassSetIterator, bool> result = classes_.insert(c);
  const Class* present = *result.first;

  // Make sure that we've assigned a string ID for this class' name
  LookupClassNameId(c);

  CHECK_EQ(present, c);
  return (HprofStringId) present;
}

int Hprof::DumpClasses() {
  HprofRecord *rec = &current_record_;
  uint32_t nextSerialNumber = 1;

  for (ClassSetIterator it = classes_.begin(); it != classes_.end(); ++it) {
    const Class* c = *it;
    CHECK(c != NULL);

    int err = StartNewRecord(HPROF_TAG_LOAD_CLASS, HPROF_TIME);
    if (err != 0) {
      return err;
    }

    // LOAD CLASS format:
    // U4: class serial number (always > 0)
    // ID: class object ID. We use the address of the class object structure as its ID.
    // U4: stack trace serial number
    // ID: class name string ID
    rec->AddU4(nextSerialNumber++);
    rec->AddId((HprofClassObjectId) c);
    rec->AddU4(HPROF_NULL_STACK_TRACE);
    rec->AddId(LookupClassNameId(c));
  }

  return 0;
}

static void HprofRootVisitor(const Object* obj, void* arg) {
  CHECK(arg != NULL);
  Hprof* hprof = reinterpret_cast<Hprof*>(arg);
  hprof->VisitRoot(obj);
}

static void HprofBitmapCallback(Object *obj, void *arg) {
  CHECK(obj != NULL);
  CHECK(arg != NULL);
  Hprof* hprof = reinterpret_cast<Hprof*>(arg);
  hprof->DumpHeapObject(obj);
}

/*
 * Walk the roots and heap writing heap information to the specified
 * file.
 *
 * If "fd" is >= 0, the output will be written to that file descriptor.
 * Otherwise, "file_name_" is used to create an output file.
 *
 * If "direct_to_ddms_" is set, the other arguments are ignored, and data is
 * sent directly to DDMS.
 */
void DumpHeap(const char* fileName, int fd, bool direct_to_ddms) {
  CHECK(fileName != NULL);
  ScopedHeapLock heap_lock;
  ScopedThreadStateChange tsc(Thread::Current(), kRunnable);

  ThreadList* thread_list = Runtime::Current()->GetThreadList();
  thread_list->SuspendAll();

  Runtime* runtime = Runtime::Current();
  Hprof hprof(fileName, fd, false, direct_to_ddms);
  runtime->VisitRoots(HprofRootVisitor, &hprof);
  runtime->GetHeap()->GetLiveBits()->Walk(HprofBitmapCallback, &hprof);
  // TODO: write a HEAP_SUMMARY record
  hprof.Finish();
  thread_list->ResumeAll();
}

}  // namespace hprof

}  // namespace art