/*

 * Copyright 1997-2008 Sun Microsystems, Inc.  All Rights Reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

// Types in this file:

//    relocInfo

//      One element of an array of halfwords encoding compressed relocations.

//      Also, the source of relocation types (relocInfo::oop_type, ...).

//    Relocation

//      A flyweight object representing a single relocation.

//      It is fully unpacked from the compressed relocation array.

//    oop_Relocation, ... (subclasses of Relocation)

//      The location of some type-specific operations (oop_addr, ...).

//      Also, the source of relocation specs (oop_Relocation::spec, ...).

//    RelocationHolder

//      A ValueObj type which acts as a union holding a Relocation object.

//      Represents a relocation spec passed into a CodeBuffer during assembly.

//    RelocIterator

//      A StackObj which iterates over the relocations associated with

//      a range of code addresses.  Can be used to operate a copy of code.

//    PatchingRelocIterator

//      Specialized subtype of RelocIterator which removes breakpoints

//      temporarily during iteration, then restores them.

//    BoundRelocation

//      An _internal_ type shared by packers and unpackers of relocations.

//      It pastes together a RelocationHolder with some pointers into

//      code and relocInfo streams.

// Notes on relocType:

//

// These hold enough information to read or write a value embedded in

// the instructions of an CodeBlob.  They're used to update:

//

//   1) embedded oops     (isOop()          == true)

//   2) inline caches     (isIC()           == true)

//   3) runtime calls     (isRuntimeCall()  == true)

//   4) internal word ref (isInternalWord() == true)

//   5) external word ref (isExternalWord() == true)

//

// when objects move (GC) or if code moves (compacting the code heap).

// They are also used to patch the code (if a call site must change)

//

// A relocInfo is represented in 16 bits:

//   4 bits indicating the relocation type

//  12 bits indicating the offset from the previous relocInfo address

//

// The offsets accumulate along the relocInfo stream to encode the

// address within the CodeBlob, which is named RelocIterator::addr().

// The address of a particular relocInfo always points to the first

// byte of the relevant instruction (and not to any of its subfields

// or embedded immediate constants).

//

// The offset value is scaled appropriately for the target machine.

// (See relocInfo_<arch>.hpp for the offset scaling.)

//

// On some machines, there may also be a "format" field which may provide

// additional information about the format of the instruction stream

// at the corresponding code address.  The format value is usually zero.

// Any machine (such as Intel) whose instructions can sometimes contain

// more than one relocatable constant needs format codes to distinguish

// which operand goes with a given relocation.

//

// If the target machine needs N format bits, the offset has 12-N bits,

// the format is encoded between the offset and the type, and the

// relocInfo_<arch>.hpp file has manifest constants for the format codes.

//

// If the type is "data_prefix_tag" then the offset bits are further encoded,

// and in fact represent not a code-stream offset but some inline data.

// The data takes the form of a counted sequence of halfwords, which

// precedes the actual relocation record.  (Clients never see it directly.)

// The interpetation of this extra data depends on the relocation type.

//

// On machines that have 32-bit immediate fields, there is usually

// little need for relocation "prefix" data, because the instruction stream

// is a perfectly reasonable place to store the value.  On machines in

// which 32-bit values must be "split" across instructions, the relocation

// data is the "true" specification of the value, which is then applied

// to some field of the instruction (22 or 13 bits, on SPARC).

//

// Whenever the location of the CodeBlob changes, any PC-relative

// relocations, and any internal_word_type relocations, must be reapplied.

// After the GC runs, oop_type relocations must be reapplied.

//

//

// Here are meanings of the types:

//

// relocInfo::none -- a filler record

//   Value:  none

//   Instruction: The corresponding code address is ignored

//   Data:  Any data prefix and format code are ignored

//   (This means that any relocInfo can be disabled by setting

//   its type to none.  See relocInfo::remove.)

//

// relocInfo::oop_type -- a reference to an oop

//   Value:  an oop, or else the address (handle) of an oop

//   Instruction types: memory (load), set (load address)

//   Data:  []       an oop stored in 4 bytes of instruction

//          [n]      n is the index of an oop in the CodeBlob's oop pool

//          [[N]n l] and l is a byte offset to be applied to the oop

//          [Nn Ll]  both index and offset may be 32 bits if necessary

//   Here is a special hack, used only by the old compiler:

//          [[N]n 00] the value is the __address__ of the nth oop in the pool

//   (Note that the offset allows optimal references to class variables.)

//

// relocInfo::internal_word_type -- an address within the same CodeBlob

// relocInfo::section_word_type -- same, but can refer to another section

//   Value:  an address in the CodeBlob's code or constants section

//   Instruction types: memory (load), set (load address)

//   Data:  []     stored in 4 bytes of instruction

//          [[L]l] a relative offset (see [About Offsets] below)

//   In the case of section_word_type, the offset is relative to a section

//   base address, and the section number (e.g., SECT_INSTS) is encoded

//   into the low two bits of the offset L.

//

// relocInfo::external_word_type -- a fixed address in the runtime system

//   Value:  an address

//   Instruction types: memory (load), set (load address)

//   Data:  []   stored in 4 bytes of instruction

//          [n]  the index of a "well-known" stub (usual case on RISC)

//          [Ll] a 32-bit address

//

// relocInfo::runtime_call_type -- a fixed subroutine in the runtime system

//   Value:  an address

//   Instruction types: PC-relative call (or a PC-relative branch)

//   Data:  []   stored in 4 bytes of instruction

//

// relocInfo::static_call_type -- a static call

//   Value:  an CodeBlob, a stub, or a fixup routine

//   Instruction types: a call

//   Data:  []

//   The identity of the callee is extracted from debugging information.

//   //%note reloc_3

//

// relocInfo::virtual_call_type -- a virtual call site (which includes an inline

//                                 cache)

//   Value:  an CodeBlob, a stub, the interpreter, or a fixup routine

//   Instruction types: a call, plus some associated set-oop instructions

//   Data:  []       the associated set-oops are adjacent to the call

//          [n]      n is a relative offset to the first set-oop

//          [[N]n l] and l is a limit within which the set-oops occur

//          [Nn Ll]  both n and l may be 32 bits if necessary

//   The identity of the callee is extracted from debugging information.

//

// relocInfo::opt_virtual_call_type -- a virtual call site that is statically bound

//

//    Same info as a static_call_type. We use a special type, so the handling of

//    virtuals and statics are separated.

//

//

//   The offset n points to the first set-oop.  (See [About Offsets] below.)

//   In turn, the set-oop instruction specifies or contains an oop cell devoted

//   exclusively to the IC call, which can be patched along with the call.

//

//   The locations of any other set-oops are found by searching the relocation

//   information starting at the first set-oop, and continuing until all

//   relocations up through l have been inspected.  The value l is another

//   relative offset.  (Both n and l are relative to the call's first byte.)

//

//   The limit l of the search is exclusive.  However, if it points within

//   the call (e.g., offset zero), it is adjusted to point after the call and

//   any associated machine-specific delay slot.

//

//   Since the offsets could be as wide as 32-bits, these conventions

//   put no restrictions whatever upon code reorganization.

//

//   The compiler is responsible for ensuring that transition from a clean

//   state to a monomorphic compiled state is MP-safe.  This implies that

//   the system must respond well to intermediate states where a random

//   subset of the set-oops has been correctly from the clean state

//   upon entry to the VEP of the compiled method.  In the case of a

//   machine (Intel) with a single set-oop instruction, the 32-bit

//   immediate field must not straddle a unit of memory coherence.

//   //%note reloc_3

//

// relocInfo::breakpoint_type -- a conditional breakpoint in the code

//   Value:  none

//   Instruction types: any whatsoever

//   Data:  [b [T]t  i...]

//   The b is a bit-packed word representing the breakpoint's attributes.

//   The t is a target address which the breakpoint calls (when it is enabled).

//   The i... is a place to store one or two instruction words overwritten

//   by a trap, so that the breakpoint may be subsequently removed.

//

// relocInfo::static_stub_type -- an extra stub for each static_call_type

//   Value:  none

//   Instruction types: a virtual call:  { set_oop; jump; }

//   Data:  [[N]n]  the offset of the associated static_call reloc

//   This stub becomes the target of a static call which must be upgraded

//   to a virtual call (because the callee is interpreted).

//   See [About Offsets] below.

//   //%note reloc_2

//

// For example:

//

//   INSTRUCTIONS                        RELOC: TYPE    PREFIX DATA

//   ------------                               ----    -----------

// sethi      %hi(myObject),  R               oop_type [n(myObject)]

// ld      [R+%lo(myObject)+fldOffset], R2    oop_type [n(myObject) fldOffset]

// add R2, 1, R2

// st  R2, [R+%lo(myObject)+fldOffset]        oop_type [n(myObject) fldOffset]

//%note reloc_1

//

// This uses 4 instruction words, 8 relocation halfwords,

// and an entry (which is sharable) in the CodeBlob's oop pool,

// for a total of 36 bytes.

//

// Note that the compiler is responsible for ensuring the "fldOffset" when

// added to "%lo(myObject)" does not overflow the immediate fields of the

// memory instructions.

//

//

// [About Offsets] Relative offsets are supplied to this module as

// positive byte offsets, but they may be internally stored scaled

// and/or negated, depending on what is most compact for the target

// system.  Since the object pointed to by the offset typically

// precedes the relocation address, it is profitable to store

// these negative offsets as positive numbers, but this decision

// is internal to the relocation information abstractions.

//

class Relocation;

class CodeBuffer;

class CodeSection;

class RelocIterator;

class relocInfo VALUE_OBJ_CLASS_SPEC {

  friend class RelocIterator;

 public:

  enum relocType {

    none                    =  0, // Used when no relocation should be generated

    oop_type                =  1, // embedded oop

    virtual_call_type       =  2, // a standard inline cache call for a virtual send

    opt_virtual_call_type   =  3, // a virtual call that has been statically bound (i.e., no IC cache)

    static_call_type        =  4, // a static send

    static_stub_type        =  5, // stub-entry for static send  (takes care of interpreter case)

    runtime_call_type       =  6, // call to fixed external routine

    external_word_type      =  7, // reference to fixed external address

    internal_word_type      =  8, // reference within the current code blob

    section_word_type       =  9, // internal, but a cross-section reference

    poll_type               = 10, // polling instruction for safepoints

    poll_return_type        = 11, // polling instruction for safepoints at return

    breakpoint_type         = 12, // an initialization barrier or safepoint

    yet_unused_type         = 13, // Still unused

    yet_unused_type_2       = 14, // Still unused

    data_prefix_tag         = 15, // tag for a prefix (carries data arguments)

    type_mask               = 15  // A mask which selects only the above values

  };

 protected:

  unsigned short _value;

  enum RawBitsToken { RAW_BITS };

  relocInfo(relocType type, RawBitsToken ignore, int bits)

    : _value((type << nontype_width) + bits) { }

  relocInfo(relocType type, RawBitsToken ignore, int off, int f)

    : _value((type << nontype_width) + (off / (unsigned)offset_unit) + (f << offset_width)) { }

 public:

  // constructor

  relocInfo(relocType type, int offset, int format = 0)

#ifndef ASSERT

  {

    (*this) = relocInfo(type, RAW_BITS, offset, format);

  }

#else

  // Put a bunch of assertions out-of-line.

  ;

#endif

  #define APPLY_TO_RELOCATIONS(visitor) \

    visitor(oop) \

    visitor(virtual_call) \

    visitor(opt_virtual_call) \

    visitor(static_call) \

    visitor(static_stub) \

    visitor(runtime_call) \

    visitor(external_word) \

    visitor(internal_word) \

    visitor(poll) \

    visitor(poll_return) \

    visitor(breakpoint) \

    visitor(section_word) \

 public:

  enum {

    value_width             = sizeof(unsigned short) * BitsPerByte,

    type_width              = 4,   // == log2(type_mask+1)

    nontype_width           = value_width - type_width,

    datalen_width           = nontype_width-1,

    datalen_tag             = 1 << datalen_width,  // or-ed into _value

    datalen_limit           = 1 << datalen_width,

    datalen_mask            = (1 << datalen_width)-1

  };

  // accessors

 public:

  relocType  type()       const { return (relocType)((unsigned)_value >> nontype_width); }

  int  format()           const { return format_mask==0? 0: format_mask &

                                         ((unsigned)_value >> offset_width); }

  int  addr_offset()      const { assert(!is_prefix(), "must have offset");

                                  return (_value & offset_mask)*offset_unit; }

 protected:

  const short* data()     const { assert(is_datalen(), "must have data");

                                  return (const short*)(this + 1); }

  int          datalen()  const { assert(is_datalen(), "must have data");

                                  return (_value & datalen_mask); }

  int         immediate() const { assert(is_immediate(), "must have immed");

                                  return (_value & datalen_mask); }

 public:

  static int addr_unit()        { return offset_unit; }

  static int offset_limit()     { return (1 << offset_width) * offset_unit; }

  void set_type(relocType type);

  void set_format(int format);

  void remove() { set_type(none); }

 protected:

  bool is_none()                const { return type() == none; }

  bool is_prefix()              const { return type() == data_prefix_tag; }

  bool is_datalen()             const { assert(is_prefix(), "must be prefix");

                                        return (_value & datalen_tag) != 0; }

  bool is_immediate()           const { assert(is_prefix(), "must be prefix");

                                        return (_value & datalen_tag) == 0; }

 public:

  // Occasionally records of type relocInfo::none will appear in the stream.

  // We do not bother to filter these out, but clients should ignore them.

  // These records serve as "filler" in three ways:

  //  - to skip large spans of unrelocated code (this is rare)

  //  - to pad out the relocInfo array to the required oop alignment

  //  - to disable old relocation information which is no longer applicable

  inline friend relocInfo filler_relocInfo();

  // Every non-prefix relocation may be preceded by at most one prefix,

  // which supplies 1 or more halfwords of associated data.  Conventionally,

  // an int is represented by 0, 1, or 2 halfwords, depending on how

  // many bits are required to represent the value.  (In addition,

  // if the sole halfword is a 10-bit unsigned number, it is made

  // "immediate" in the prefix header word itself.  This optimization

  // is invisible outside this module.)

  inline friend relocInfo prefix_relocInfo(int datalen = 0);

 protected:

  // an immediate relocInfo optimizes a prefix with one 10-bit unsigned value

  static relocInfo immediate_relocInfo(int data0) {

    assert(fits_into_immediate(data0), "data0 in limits");

    return relocInfo(relocInfo::data_prefix_tag, RAW_BITS, data0);

  }

  static bool fits_into_immediate(int data0) {

    return (data0 >= 0 && data0 < datalen_limit);

  }

 public:

  // Support routines for compilers.

  // This routine takes an infant relocInfo (unprefixed) and

  // edits in its prefix, if any.  It also updates dest.locs_end.

  void initialize(CodeSection* dest, Relocation* reloc);

  // This routine updates a prefix and returns the limit pointer.

  // It tries to compress the prefix from 32 to 16 bits, and if

  // successful returns a reduced "prefix_limit" pointer.

  relocInfo* finish_prefix(short* prefix_limit);

  // bit-packers for the data array:

  // As it happens, the bytes within the shorts are ordered natively,

  // but the shorts within the word are ordered big-endian.

  // This is an arbitrary choice, made this way mainly to ease debugging.

  static int data0_from_int(jint x)         { return x >> value_width; }

  static int data1_from_int(jint x)         { return (short)x; }

  static jint jint_from_data(short* data) {

    return (data[0] << value_width) + (unsigned short)data[1];

  }

  static jint short_data_at(int n, short* data, int datalen) {

    return datalen > n ? data[n] : 0;

  }

  static jint jint_data_at(int n, short* data, int datalen) {

    return datalen > n+1 ? jint_from_data(&data[n]) : short_data_at(n, data, datalen);

  }

  // Update methods for relocation information

  // (since code is dynamically patched, we also need to dynamically update the relocation info)

  // Both methods takes old_type, so it is able to performe sanity checks on the information removed.

  static void change_reloc_info_for_address(RelocIterator *itr, address pc, relocType old_type, relocType new_type);

  static void remove_reloc_info_for_address(RelocIterator *itr, address pc, relocType old_type);

  // Machine dependent stuff

  #include "incls/_relocInfo_pd.hpp.incl"

 protected:

  // Derived constant, based on format_width which is PD:

  enum {

    offset_width       = nontype_width - format_width,

    offset_mask        = (1<<offset_width) - 1,

    format_mask        = (1<<format_width) - 1

  };

 public:

  enum {

    // Conservatively large estimate of maximum length (in shorts)

    // of any relocation record (probably breakpoints are largest).

    // Extended format is length prefix, data words, and tag/offset suffix.

    length_limit       = 1 + 1 + (3*BytesPerWord/BytesPerShort) + 1,

    have_format        = format_width > 0

  };

};

#define FORWARD_DECLARE_EACH_CLASS(name)              \

class name##_Relocation;

APPLY_TO_RELOCATIONS(FORWARD_DECLARE_EACH_CLASS)

#undef FORWARD_DECLARE_EACH_CLASS

inline relocInfo filler_relocInfo() {

  return relocInfo(relocInfo::none, relocInfo::offset_limit() - relocInfo::offset_unit);

}

inline relocInfo prefix_relocInfo(int datalen) {

  assert(relocInfo::fits_into_immediate(datalen), "datalen in limits");

  return relocInfo(relocInfo::data_prefix_tag, relocInfo::RAW_BITS, relocInfo::datalen_tag | datalen);

}

// Holder for flyweight relocation objects.

// Although the flyweight subclasses are of varying sizes,

// the holder is "one size fits all".

class RelocationHolder VALUE_OBJ_CLASS_SPEC {

  friend class Relocation;

  friend class CodeSection;

 private:

  // this preallocated memory must accommodate all subclasses of Relocation

  // (this number is assertion-checked in Relocation::operator new)

  enum { _relocbuf_size = 5 };

  void* _relocbuf[ _relocbuf_size ];

 public:

  Relocation* reloc() const { return (Relocation*) &_relocbuf[0]; }

  inline relocInfo::relocType type() const;

  // Add a constant offset to a relocation.  Helper for class Address.

  RelocationHolder plus(int offset) const;

  inline RelocationHolder();                // initializes type to none

  inline RelocationHolder(Relocation* r);   // make a copy

  static const RelocationHolder none;

};

// A RelocIterator iterates through the relocation information of a CodeBlob.

// It is a variable BoundRelocation which is able to take on successive

// values as it is advanced through a code stream.

// Usage:

//   RelocIterator iter(nm);

//   while (iter.next()) {

//     iter.reloc()->some_operation();

//   }

// or:

//   RelocIterator iter(nm);

//   while (iter.next()) {

//     switch (iter.type()) {

//      case relocInfo::oop_type          :

//      case relocInfo::ic_type           :

//      case relocInfo::prim_type         :

//      case relocInfo::uncommon_type     :

//      case relocInfo::runtime_call_type :

//      case relocInfo::internal_word_type:

//      case relocInfo::external_word_type:

//      ...

//     }

//   }

class RelocIterator : public StackObj {

  enum { SECT_CONSTS = 2,

         SECT_LIMIT = 3 };  // must be equal to CodeBuffer::SECT_LIMIT

  friend class Relocation;

  friend class relocInfo;       // for change_reloc_info_for_address only

  typedef relocInfo::relocType relocType;

 private:

  address    _limit;   // stop producing relocations after this _addr

  relocInfo* _current; // the current relocation information

  relocInfo* _end;     // end marker; we're done iterating when _current == _end

  CodeBlob*  _code;    // compiled method containing _addr

  address    _addr;    // instruction to which the relocation applies

  short      _databuf; // spare buffer for compressed data

  short*     _data;    // pointer to the relocation's data

  short      _datalen; // number of halfwords in _data

  char       _format;  // position within the instruction

  // Base addresses needed to compute targets of section_word_type relocs.

  address    _section_start[SECT_LIMIT];

  void set_has_current(bool b) {

    _datalen = !b ? -1 : 0;

    debug_only(_data = NULL);

  }