1 /*
  2  * Copyright (c) 2020, Oracle and/or its affiliates. All rights reserved.
  3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  4  *
  5  * This code is free software; you can redistribute it and/or modify it
  6  * under the terms of the GNU General Public License version 2 only, as
  7  * published by the Free Software Foundation.
  8  *
  9  * This code is distributed in the hope that it will be useful, but WITHOUT
 10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 12  * version 2 for more details (a copy is included in the LICENSE file that
 13  * accompanied this code).
 14  *
 15  * You should have received a copy of the GNU General Public License version
 16  * 2 along with this work; if not, write to the Free Software Foundation,
 17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 18  *
 19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 20  * or visit www.oracle.com if you need additional information or have any
 21  * questions.
 22  *
 23  */
 24 
 25 #ifndef SHARE_CLASSFILE_FIELDLAYOUTBUILDER_HPP
 26 #define SHARE_CLASSFILE_FIELDLAYOUTBUILDER_HPP
 27 
 28 #include "classfile/classFileParser.hpp"
 29 #include "classfile/classLoaderData.hpp"
 30 #include "memory/allocation.hpp"
 31 #include "oops/fieldStreams.hpp"
 32 #include "utilities/growableArray.hpp"
 33 
 34 // Classes below are used to compute the field layout of classes.
 35 
 36 
 37 // A LayoutRawBlock describes an element of a layout.
 38 // Each field is represented by a LayoutRawBlock.
 39 // LayoutRawBlocks can also represent elements injected by the JVM:
 40 // padding, empty blocks, inherited fields, etc.
 41 // All LayoutRawBlocks must have a size and an alignment. The size is the
 42 // exact size of the field expressed in bytes. The alignment is
 43 // the alignment constraint of the field (1 for byte, 2 for short,
 44 // 4 for int, 8 for long, etc.)
 45 //
 46 // LayoutRawBlock are designed to be used in two data structures:
 47 //   - a linked list in a layout (using _next_block, _prev_block)
 48 //   - a GrowableArray in field group (the growable array contains pointers to LayoutRawBlocks)
 49 //
 50 //  next/prev pointers are included in the LayoutRawBlock class to narrow
 51 //  the number of allocation required during the computation of a layout.
 52 //
 53 class LayoutRawBlock : public ResourceObj {
 54  public:
 55   // Some code relies on the order of values below.
 56   enum Kind {
 57     EMPTY,         // empty slot, space is taken from this to allocate fields
 58     RESERVED,      // reserved for JVM usage (for instance object header)
 59     PADDING,       // padding (because of alignment constraints or @Contended)
 60     REGULAR,       // primitive or oop field (including non-flattened inline fields)
 61     FLATTENED,     // flattened field
 62     INHERITED      // field(s) inherited from super classes
 63   };
 64 
 65  private:
 66   LayoutRawBlock* _next_block;
 67   LayoutRawBlock* _prev_block;
 68   Kind _kind;
 69   int _offset;
 70   int _alignment;
 71   int _size;
 72   int _field_index;
 73   bool _is_reference;
 74 
 75  public:
 76   LayoutRawBlock(Kind kind, int size);
 77   LayoutRawBlock(int index, Kind kind, int size, int alignment, bool is_reference = false);
 78   LayoutRawBlock* next_block() const { return _next_block; }
 79   void set_next_block(LayoutRawBlock* next) { _next_block = next; }
 80   LayoutRawBlock* prev_block() const { return _prev_block; }
 81   void set_prev_block(LayoutRawBlock* prev) { _prev_block = prev; }
 82   Kind kind() const { return _kind; }
 83   int offset() const {
 84     assert(_offset >= 0, "Must be initialized");
 85     return _offset;
 86   }
 87   void set_offset(int offset) { _offset = offset; }
 88   int alignment() const { return _alignment; }
 89   int size() const { return _size; }
 90   void set_size(int size) { _size = size; }
 91   int field_index() const {
 92     assert(_field_index != -1, "Must be initialized");
 93     return _field_index;
 94   }
 95   bool is_reference() const { return _is_reference; }
 96 
 97   bool fit(int size, int alignment);
 98 
 99   static int compare_offset(LayoutRawBlock** x, LayoutRawBlock** y)  { return (*x)->offset() - (*y)->offset(); }
100   // compare_size_inverted() returns the opposite of a regular compare method in order to
101   // sort fields in decreasing order.
102   // Note: with line types, the comparison should include alignment constraint if sizes are equals
103   static int compare_size_inverted(LayoutRawBlock** x, LayoutRawBlock** y)  {
104 #ifdef _WINDOWS
105     // qsort() on Windows reverse the order of fields with the same size
106     // the extension of the comparison function below preserves this order
107     int diff = (*y)->size() - (*x)->size();
108     if (diff == 0) {
109       diff = (*x)->field_index() - (*y)->field_index();
110     }
111     return diff;
112 #else
113     return (*y)->size() - (*x)->size();
114 #endif // _WINDOWS
115   }
116 
117 };
118 
119 // A Field group represents a set of fields that have to be allocated together,
120 // this is the way the @Contended annotation is supported.
121 // Inside a FieldGroup, fields are sorted based on their kind: primitive,
122 // oop, or flattened.
123 //
124 class FieldGroup : public ResourceObj {
125 
126  private:
127   FieldGroup* _next;
128   GrowableArray<LayoutRawBlock*>* _primitive_fields;
129   GrowableArray<LayoutRawBlock*>* _oop_fields;
130   int _contended_group;
131   int _oop_count;
132   static const int INITIAL_LIST_SIZE = 16;
133 
134  public:
135   FieldGroup(int contended_group = -1);
136 
137   FieldGroup* next() const { return _next; }
138   void set_next(FieldGroup* next) { _next = next; }
139   GrowableArray<LayoutRawBlock*>* primitive_fields() const { return _primitive_fields; }
140   GrowableArray<LayoutRawBlock*>* oop_fields() const { return _oop_fields; }
141   int contended_group() const { return _contended_group; }
142   int oop_count() const { return _oop_count; }
143 
144   void add_primitive_field(AllFieldStream fs, BasicType type);
145   void add_oop_field(AllFieldStream fs);
146   void sort_by_size();
147 };
148 
149 // The FieldLayout class represents a set of fields organized
150 // in a layout.
151 // An instance of FieldLayout can either represent the layout
152 // of non-static fields (used in an instance object) or the
153 // layout of static fields (to be included in the class mirror).
154 //
155 // _block is a pointer to a list of LayoutRawBlock ordered by increasing
156 // offsets.
157 // _start points to the LayoutRawBlock with the first offset that can
158 // be used to allocate fields of the current class
159 // _last points to the last LayoutRawBlock of the list. In order to
160 // simplify the code, the LayoutRawBlock list always ends with an
161 // EMPTY block (the kind of LayoutRawBlock from which space is taken
162 // to allocate fields) with a size big enough to satisfy all
163 // field allocations.
164 //
165 class FieldLayout : public ResourceObj {
166  private:
167   Array<u2>* _fields;
168   ConstantPool* _cp;
169   LayoutRawBlock* _blocks;  // the layout being computed
170   LayoutRawBlock* _start;   // points to the first block where a field can be inserted
171   LayoutRawBlock* _last;    // points to the last block of the layout (big empty block)
172 
173  public:
174   FieldLayout(Array<u2>* fields, ConstantPool* cp);
175   void initialize_static_layout();
176   void initialize_instance_layout(const InstanceKlass* ik);
177 
178   LayoutRawBlock* first_empty_block() {
179     LayoutRawBlock* block = _start;
180     while (block->kind() != LayoutRawBlock::EMPTY) {
181       block = block->next_block();
182     }
183     return block;
184   }
185 
186   LayoutRawBlock* start() { return _start; }
187   void set_start(LayoutRawBlock* start) { _start = start; }
188   LayoutRawBlock* last_block() { return _last; }
189 
190   LayoutRawBlock* first_field_block();
191   void add(GrowableArray<LayoutRawBlock*>* list, LayoutRawBlock* start = NULL);
192   void add_field_at_offset(LayoutRawBlock* blocks, int offset, LayoutRawBlock* start = NULL);
193   void add_contiguously(GrowableArray<LayoutRawBlock*>* list, LayoutRawBlock* start = NULL);
194   LayoutRawBlock* insert_field_block(LayoutRawBlock* slot, LayoutRawBlock* block);
195   bool reconstruct_layout(const InstanceKlass* ik);
196   void fill_holes(const InstanceKlass* ik);
197   LayoutRawBlock* insert(LayoutRawBlock* slot, LayoutRawBlock* block);
198   void remove(LayoutRawBlock* block);
199   void print(outputStream* output, bool is_static, const InstanceKlass* super);
200 };
201 
202 
203 // FieldLayoutBuilder is the main entry point for layout computation.
204 // This class has three methods to generate layout: one for regular classes
205 // and two for classes with hard coded offsets (java,lang.ref.Reference
206 // and the boxing classes). The rationale for having multiple methods
207 // is that each kind of class has a different set goals regarding
208 // its layout, so instead of mixing several layout strategies into a
209 // single method, each kind has its own method (see comments below
210 // for more details about the allocation strategies).
211 //
212 // Computing the layout of a class always goes through 4 steps:
213 //   1 - Prologue: preparation of data structure and gathering of
214 //       layout information inherited from super classes
215 //   2 - Field sorting: fields are sorted according to their
216 //       kind (oop, primitive, inline class) and their contention
217 //       annotation (if any)
218 //   3 - Layout is computed from the set of lists generated during
219 //       step 2
220 //   4 - Epilogue: oopmaps are generated, layout information is
221 //       prepared so other VM components can use it (instance size,
222 //       static field size, non-static field size, etc.)
223 //
224 //  Steps 1 and 4 are common to all layout computations. Step 2 and 3
225 //  can vary with the allocation strategy.
226 //
227 class FieldLayoutBuilder : public ResourceObj {
228  private:
229 
230   const Symbol* _classname;
231   const InstanceKlass* _super_klass;
232   ConstantPool* _constant_pool;
233   Array<u2>* _fields;
234   FieldLayoutInfo* _info;
235   FieldGroup* _root_group;
236   GrowableArray<FieldGroup*> _contended_groups;
237   FieldGroup* _static_fields;
238   FieldLayout* _layout;
239   FieldLayout* _static_layout;
240   int _nonstatic_oopmap_count;
241   int _alignment;
242   bool _has_nonstatic_fields;
243   bool _is_contended; // is a contended class?
244 
245  public:
246   FieldLayoutBuilder(const Symbol* classname, const InstanceKlass* super_klass, ConstantPool* constant_pool,
247                      Array<u2>* fields, bool is_contended, FieldLayoutInfo* info);
248 
249   int get_alignment() {
250     assert(_alignment != -1, "Uninitialized");
251     return _alignment;
252   }
253 
254   void build_layout();
255   void compute_regular_layout();
256   void insert_contended_padding(LayoutRawBlock* slot);
257 
258  private:
259   void prologue();
260   void epilogue();
261   void regular_field_sorting();
262   FieldGroup* get_or_create_contended_group(int g);
263 };
264 
265 #endif // SHARE_CLASSFILE_FIELDLAYOUTBUILDER_HPP