Filling hole between subclass and superclass.
Subclasses no longer need to be 4-byte aligned at the end. Any gaps
between a superclass and its subclasses will be filled in by halfword
or byte fields if possible.
Refactored the alignment and shuffling methods to use a priority queue
in order to reduce the amount of logic when laying out objects.
Change-Id: Ifed71af534e0c5e77bb14555c44b973fe66df6da
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index 4123fc6..fdf2958 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -18,6 +18,7 @@
#include <deque>
#include <memory>
+#include <queue>
#include <string>
#include <utility>
#include <vector>
@@ -133,6 +134,88 @@
return hash;
}
+// Gap between two fields in object layout.
+struct FieldGap {
+ uint32_t start_offset; // The offset from the start of the object.
+ uint32_t size; // The gap size of 1, 2, or 4 bytes.
+};
+struct FieldGapsComparator {
+ explicit FieldGapsComparator() {
+ }
+ bool operator() (const FieldGap& lhs, const FieldGap& rhs)
+ NO_THREAD_SAFETY_ANALYSIS {
+ // Sort by gap size, largest first.
+ return lhs.size > rhs.size;
+ }
+};
+typedef std::priority_queue<FieldGap, std::vector<FieldGap>, FieldGapsComparator> FieldGaps;
+
+// Adds largest aligned gaps to queue of gaps.
+void AddFieldGap(uint32_t gap_start, uint32_t gap_end, FieldGaps* gaps) {
+ DCHECK(gaps != nullptr);
+
+ uint32_t current_offset = gap_start;
+ while (current_offset != gap_end) {
+ size_t remaining = gap_end - current_offset;
+ if (remaining >= sizeof(uint32_t) && IsAligned<4>(current_offset)) {
+ gaps->push(FieldGap {current_offset, sizeof(uint32_t)});
+ current_offset += sizeof(uint32_t);
+ } else if (remaining >= sizeof(uint16_t) && IsAligned<2>(current_offset)) {
+ gaps->push(FieldGap {current_offset, sizeof(uint16_t)});
+ current_offset += sizeof(uint16_t);
+ } else {
+ gaps->push(FieldGap {current_offset, sizeof(uint8_t)});
+ current_offset += sizeof(uint8_t);
+ }
+ DCHECK_LE(current_offset, gap_end) << "Overran gap";
+ }
+}
+// Shuffle fields forward, making use of gaps whenever possible.
+template<int n>
+static void ShuffleForward(const size_t num_fields, size_t* current_field_idx,
+ MemberOffset* field_offset,
+ mirror::ObjectArray<mirror::ArtField>* fields,
+ std::deque<mirror::ArtField*>* grouped_and_sorted_fields,
+ FieldGaps* gaps)
+ SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+ DCHECK(current_field_idx != nullptr);
+ DCHECK(grouped_and_sorted_fields != nullptr);
+ DCHECK(fields != nullptr || (num_fields == 0 && grouped_and_sorted_fields->empty()));
+ DCHECK(gaps != nullptr);
+ DCHECK(field_offset != nullptr);
+
+ DCHECK(IsPowerOfTwo(n));
+ while (!grouped_and_sorted_fields->empty()) {
+ mirror::ArtField* field = grouped_and_sorted_fields->front();
+ Primitive::Type type = field->GetTypeAsPrimitiveType();
+ if (Primitive::ComponentSize(type) < n) {
+ break;
+ }
+ if (!IsAligned<n>(field_offset->Uint32Value())) {
+ MemberOffset old_offset = *field_offset;
+ *field_offset = MemberOffset(RoundUp(field_offset->Uint32Value(), n));
+ AddFieldGap(old_offset.Uint32Value(), field_offset->Uint32Value(), gaps);
+ }
+ CHECK(type != Primitive::kPrimNot) << PrettyField(field); // should be primitive types
+ grouped_and_sorted_fields->pop_front();
+ fields->Set<false>(*current_field_idx, field);
+ if (!gaps->empty() && gaps->top().size >= n) {
+ FieldGap gap = gaps->top();
+ gaps->pop();
+ DCHECK(IsAligned<n>(gap.start_offset));
+ field->SetOffset(MemberOffset(gap.start_offset));
+ if (gap.size > n) {
+ AddFieldGap(gap.start_offset + n, gap.start_offset + gap.size, gaps);
+ }
+ } else {
+ DCHECK(IsAligned<n>(field_offset->Uint32Value()));
+ field->SetOffset(*field_offset);
+ *field_offset = MemberOffset(field_offset->Uint32Value() + n);
+ }
+ ++(*current_field_idx);
+ }
+}
+
const char* ClassLinker::class_roots_descriptors_[] = {
"Ljava/lang/Class;",
"Ljava/lang/Object;",
@@ -2483,88 +2566,7 @@
have_portable_code);
}
-template<int n>
-void ClassLinker::AlignFields(size_t& current_field, const size_t num_fields,
- MemberOffset& field_offset,
- mirror::ObjectArray<mirror::ArtField>* fields,
- std::deque<mirror::ArtField*>& grouped_and_sorted_fields) {
- if (current_field != num_fields && !IsAligned<n>(field_offset.Uint32Value())) {
- size_t gap = (n - (field_offset.Uint32Value() & (n - 1)));
- // Avoid padding unless a field that requires alignment actually exists.
- bool needs_padding = false;
- for (size_t i = 0; i < grouped_and_sorted_fields.size(); ++i) {
- mirror::ArtField* field = grouped_and_sorted_fields[i];
- Primitive::Type type = field->GetTypeAsPrimitiveType();
- CHECK(type != Primitive::kPrimNot) << PrettyField(field); // should be primitive types
- // Too big to fill the gap.
- if (Primitive::ComponentSize(type) >= n) {
- needs_padding = true;
- continue;
- }
- if (needs_padding) {
- // Shift as many fields as possible to fill the gaps.
- size_t cursor = i;
- mirror::ArtField* shift_field;
- Primitive::Type shift_type;
- while (cursor < grouped_and_sorted_fields.size() && gap > 0) {
- // Find field that can current in current gap.
- do {
- DCHECK_LT(cursor, grouped_and_sorted_fields.size()) << "Cursor overran fields.";
- shift_field = grouped_and_sorted_fields[cursor];
- shift_type = shift_field->GetTypeAsPrimitiveType();
- CHECK(shift_type != Primitive::kPrimNot) << PrettyField(shift_field);
- // Can fit.
- if (Primitive::ComponentSize(shift_type) <= gap) {
- break;
- }
- ++cursor;
- } while (cursor < grouped_and_sorted_fields.size());
- if (cursor < grouped_and_sorted_fields.size()) {
- fields->Set<false>(current_field++, shift_field);
- shift_field->SetOffset(field_offset);
- field_offset = MemberOffset(field_offset.Uint32Value() +
- Primitive::ComponentSize(shift_type));
- gap -= Primitive::ComponentSize(shift_type);
- grouped_and_sorted_fields.erase(grouped_and_sorted_fields.begin() + cursor);
- }
- }
- }
- break;
- }
- // No further shuffling available, pad whatever space is left.
- if (needs_padding) {
- field_offset = MemberOffset(field_offset.Uint32Value() + gap);
- }
- DCHECK(!needs_padding || IsAligned<n>(field_offset.Uint32Value())) << "Needed " <<
- n << " byte alignment, but not aligned after align with offset: " <<
- field_offset.Uint32Value();
- }
-}
-
-template<int n>
-void ClassLinker::ShuffleForward(size_t ¤t_field, const size_t num_fields,
- MemberOffset& field_offset,
- mirror::ObjectArray<mirror::ArtField>* fields,
- std::deque<mirror::ArtField*>& grouped_and_sorted_fields) {
- while (!grouped_and_sorted_fields.empty() && current_field != num_fields) {
- mirror::ArtField* field = grouped_and_sorted_fields.front();
- Primitive::Type type = field->GetTypeAsPrimitiveType();
- CHECK(type != Primitive::kPrimNot) << PrettyField(field); // should be primitive types
- if (Primitive::ComponentSize(type) != n) {
- DCHECK_LT(Primitive::ComponentSize(type), static_cast<unsigned int>(n)) <<
- "Encountered a larger field (" << Primitive::ComponentSize(type) << ") " <<
- "while shuffling fields of size: " << n;
- // We should've shuffled all field of size n forward by this point.
- break;
- }
- DCHECK(IsAligned<n>(field_offset.Uint32Value()));
- grouped_and_sorted_fields.pop_front();
- fields->Set<false>(current_field++, field);
- field->SetOffset(field_offset);
- field_offset = MemberOffset(field_offset.Uint32Value() + n);
- }
-}
void ClassLinker::LoadClass(const DexFile& dex_file,
const DexFile::ClassDef& dex_class_def,
@@ -4830,9 +4832,11 @@
std::sort(grouped_and_sorted_fields.begin(), grouped_and_sorted_fields.end(),
LinkFieldsComparator());
- // References should be at the front, unless we need to pad.
+ // References should be at the front.
size_t current_field = 0;
size_t num_reference_fields = 0;
+ FieldGaps gaps;
+
for (; current_field < num_fields; current_field++) {
mirror::ArtField* field = grouped_and_sorted_fields.front();
Primitive::Type type = field->GetTypeAsPrimitiveType();
@@ -4840,27 +4844,31 @@
if (isPrimitive) {
break; // past last reference, move on to the next phase
}
+ if (UNLIKELY(!IsAligned<4>(field_offset.Uint32Value()))) {
+ MemberOffset old_offset = field_offset;
+ field_offset = MemberOffset(RoundUp(field_offset.Uint32Value(), 4));
+ AddFieldGap(old_offset.Uint32Value(), field_offset.Uint32Value(), &gaps);
+ }
+ DCHECK(IsAligned<4>(field_offset.Uint32Value()));
grouped_and_sorted_fields.pop_front();
num_reference_fields++;
fields->Set<false>(current_field, field);
field->SetOffset(field_offset);
field_offset = MemberOffset(field_offset.Uint32Value() + sizeof(uint32_t));
}
-
- AlignFields<8>(current_field, num_fields, field_offset, fields, grouped_and_sorted_fields);
- ShuffleForward<8>(current_field, num_fields, field_offset, fields, grouped_and_sorted_fields);
- // No need for further alignment, start of object is 4-byte aligned.
- ShuffleForward<4>(current_field, num_fields, field_offset, fields, grouped_and_sorted_fields);
- ShuffleForward<2>(current_field, num_fields, field_offset, fields, grouped_and_sorted_fields);
- ShuffleForward<1>(current_field, num_fields, field_offset, fields, grouped_and_sorted_fields);
+ // Gaps are stored as a max heap which means that we must shuffle from largest to smallest
+ // otherwise we could end up with suboptimal gap fills.
+ ShuffleForward<8>(num_fields, ¤t_field, &field_offset,
+ fields, &grouped_and_sorted_fields, &gaps);
+ ShuffleForward<4>(num_fields, ¤t_field, &field_offset,
+ fields, &grouped_and_sorted_fields, &gaps);
+ ShuffleForward<2>(num_fields, ¤t_field, &field_offset,
+ fields, &grouped_and_sorted_fields, &gaps);
+ ShuffleForward<1>(num_fields, ¤t_field, &field_offset,
+ fields, &grouped_and_sorted_fields, &gaps);
CHECK(grouped_and_sorted_fields.empty()) << "Missed " << grouped_and_sorted_fields.size() <<
" fields.";
- // Subclass expects superclass to be 4 byte aligned at end.
- if (!IsAligned<4>(field_offset.Uint32Value())) {
- field_offset = MemberOffset(RoundUp(field_offset.Uint32Value(), 4));
- }
- CHECK(IsAligned<4>(field_offset.Uint32Value()));
Thread::Current()->EndAssertNoThreadSuspension(old_no_suspend_cause);
// We lie to the GC about the java.lang.ref.Reference.referent field, so it doesn't scan it.