1 /* 2 * Copyright (C) 2009 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include "indirect_reference_table-inl.h" 18 19 #include "base/dumpable-inl.h" 20 #include "base/systrace.h" 21 #include "java_vm_ext.h" 22 #include "jni_internal.h" 23 #include "nth_caller_visitor.h" 24 #include "reference_table.h" 25 #include "runtime.h" 26 #include "scoped_thread_state_change-inl.h" 27 #include "thread.h" 28 #include "utils.h" 29 30 #include <cstdlib> 31 32 namespace art { 33 34 static constexpr bool kDumpStackOnNonLocalReference = false; 35 static constexpr bool kDebugIRT = false; 36 37 // Maximum table size we allow. 38 static constexpr size_t kMaxTableSizeInBytes = 128 * MB; 39 40 const char* GetIndirectRefKindString(const IndirectRefKind& kind) { 41 switch (kind) { 42 case kHandleScopeOrInvalid: 43 return "HandleScopeOrInvalid"; 44 case kLocal: 45 return "Local"; 46 case kGlobal: 47 return "Global"; 48 case kWeakGlobal: 49 return "WeakGlobal"; 50 } 51 return "IndirectRefKind Error"; 52 } 53 54 void IndirectReferenceTable::AbortIfNoCheckJNI(const std::string& msg) { 55 // If -Xcheck:jni is on, it'll give a more detailed error before aborting. 56 JavaVMExt* vm = Runtime::Current()->GetJavaVM(); 57 if (!vm->IsCheckJniEnabled()) { 58 // Otherwise, we want to abort rather than hand back a bad reference. 59 LOG(FATAL) << msg; 60 } else { 61 LOG(ERROR) << msg; 62 } 63 } 64 65 IndirectReferenceTable::IndirectReferenceTable(size_t max_count, 66 IndirectRefKind desired_kind, 67 ResizableCapacity resizable, 68 std::string* error_msg) 69 : segment_state_(kIRTFirstSegment), 70 kind_(desired_kind), 71 max_entries_(max_count), 72 current_num_holes_(0), 73 resizable_(resizable) { 74 CHECK(error_msg != nullptr); 75 CHECK_NE(desired_kind, kHandleScopeOrInvalid); 76 77 // Overflow and maximum check. 78 CHECK_LE(max_count, kMaxTableSizeInBytes / sizeof(IrtEntry)); 79 80 const size_t table_bytes = max_count * sizeof(IrtEntry); 81 table_mem_map_.reset(MemMap::MapAnonymous("indirect ref table", nullptr, table_bytes, 82 PROT_READ | PROT_WRITE, false, false, error_msg)); 83 if (table_mem_map_.get() == nullptr && error_msg->empty()) { 84 *error_msg = "Unable to map memory for indirect ref table"; 85 } 86 87 if (table_mem_map_.get() != nullptr) { 88 table_ = reinterpret_cast<IrtEntry*>(table_mem_map_->Begin()); 89 } else { 90 table_ = nullptr; 91 } 92 segment_state_ = kIRTFirstSegment; 93 last_known_previous_state_ = kIRTFirstSegment; 94 } 95 96 IndirectReferenceTable::~IndirectReferenceTable() { 97 } 98 99 void IndirectReferenceTable::ConstexprChecks() { 100 // Use this for some assertions. They can't be put into the header as C++ wants the class 101 // to be complete. 102 103 // Check kind. 104 static_assert((EncodeIndirectRefKind(kLocal) & (~kKindMask)) == 0, "Kind encoding error"); 105 static_assert((EncodeIndirectRefKind(kGlobal) & (~kKindMask)) == 0, "Kind encoding error"); 106 static_assert((EncodeIndirectRefKind(kWeakGlobal) & (~kKindMask)) == 0, "Kind encoding error"); 107 static_assert(DecodeIndirectRefKind(EncodeIndirectRefKind(kLocal)) == kLocal, 108 "Kind encoding error"); 109 static_assert(DecodeIndirectRefKind(EncodeIndirectRefKind(kGlobal)) == kGlobal, 110 "Kind encoding error"); 111 static_assert(DecodeIndirectRefKind(EncodeIndirectRefKind(kWeakGlobal)) == kWeakGlobal, 112 "Kind encoding error"); 113 114 // Check serial. 115 static_assert(DecodeSerial(EncodeSerial(0u)) == 0u, "Serial encoding error"); 116 static_assert(DecodeSerial(EncodeSerial(1u)) == 1u, "Serial encoding error"); 117 static_assert(DecodeSerial(EncodeSerial(2u)) == 2u, "Serial encoding error"); 118 static_assert(DecodeSerial(EncodeSerial(3u)) == 3u, "Serial encoding error"); 119 120 // Table index. 121 static_assert(DecodeIndex(EncodeIndex(0u)) == 0u, "Index encoding error"); 122 static_assert(DecodeIndex(EncodeIndex(1u)) == 1u, "Index encoding error"); 123 static_assert(DecodeIndex(EncodeIndex(2u)) == 2u, "Index encoding error"); 124 static_assert(DecodeIndex(EncodeIndex(3u)) == 3u, "Index encoding error"); 125 } 126 127 bool IndirectReferenceTable::IsValid() const { 128 return table_mem_map_.get() != nullptr; 129 } 130 131 // Holes: 132 // 133 // To keep the IRT compact, we want to fill "holes" created by non-stack-discipline Add & Remove 134 // operation sequences. For simplicity and lower memory overhead, we do not use a free list or 135 // similar. Instead, we scan for holes, with the expectation that we will find holes fast as they 136 // are usually near the end of the table (see the header, TODO: verify this assumption). To avoid 137 // scans when there are no holes, the number of known holes should be tracked. 138 // 139 // A previous implementation stored the top index and the number of holes as the segment state. 140 // This constraints the maximum number of references to 16-bit. We want to relax this, as it 141 // is easy to require more references (e.g., to list all classes in large applications). Thus, 142 // the implicitly stack-stored state, the IRTSegmentState, is only the top index. 143 // 144 // Thus, hole count is a local property of the current segment, and needs to be recovered when 145 // (or after) a frame is pushed or popped. To keep JNI transitions simple (and inlineable), we 146 // cannot do work when the segment changes. Thus, Add and Remove need to ensure the current 147 // hole count is correct. 148 // 149 // To be able to detect segment changes, we require an additional local field that can describe 150 // the known segment. This is last_known_previous_state_. The requirement will become clear with 151 // the following (some non-trivial) cases that have to be supported: 152 // 153 // 1) Segment with holes (current_num_holes_ > 0), push new segment, add/remove reference 154 // 2) Segment with holes (current_num_holes_ > 0), pop segment, add/remove reference 155 // 3) Segment with holes (current_num_holes_ > 0), push new segment, pop segment, add/remove 156 // reference 157 // 4) Empty segment, push new segment, create a hole, pop a segment, add/remove a reference 158 // 5) Base segment, push new segment, create a hole, pop a segment, push new segment, add/remove 159 // reference 160 // 161 // Storing the last known *previous* state (bottom index) allows conservatively detecting all the 162 // segment changes above. The condition is simply that the last known state is greater than or 163 // equal to the current previous state, and smaller than the current state (top index). The 164 // condition is conservative as it adds O(1) overhead to operations on an empty segment. 165 166 static size_t CountNullEntries(const IrtEntry* table, size_t from, size_t to) { 167 size_t count = 0; 168 for (size_t index = from; index != to; ++index) { 169 if (table[index].GetReference()->IsNull()) { 170 count++; 171 } 172 } 173 return count; 174 } 175 176 void IndirectReferenceTable::RecoverHoles(IRTSegmentState prev_state) { 177 if (last_known_previous_state_.top_index >= segment_state_.top_index || 178 last_known_previous_state_.top_index < prev_state.top_index) { 179 const size_t top_index = segment_state_.top_index; 180 size_t count = CountNullEntries(table_, prev_state.top_index, top_index); 181 182 if (kDebugIRT) { 183 LOG(INFO) << "+++ Recovered holes: " 184 << " Current prev=" << prev_state.top_index 185 << " Current top_index=" << top_index 186 << " Old num_holes=" << current_num_holes_ 187 << " New num_holes=" << count; 188 } 189 190 current_num_holes_ = count; 191 last_known_previous_state_ = prev_state; 192 } else if (kDebugIRT) { 193 LOG(INFO) << "No need to recover holes"; 194 } 195 } 196 197 ALWAYS_INLINE 198 static inline void CheckHoleCount(IrtEntry* table, 199 size_t exp_num_holes, 200 IRTSegmentState prev_state, 201 IRTSegmentState cur_state) { 202 if (kIsDebugBuild) { 203 size_t count = CountNullEntries(table, prev_state.top_index, cur_state.top_index); 204 CHECK_EQ(exp_num_holes, count) << "prevState=" << prev_state.top_index 205 << " topIndex=" << cur_state.top_index; 206 } 207 } 208 209 bool IndirectReferenceTable::Resize(size_t new_size, std::string* error_msg) { 210 CHECK_GT(new_size, max_entries_); 211 212 constexpr size_t kMaxEntries = kMaxTableSizeInBytes / sizeof(IrtEntry); 213 if (new_size > kMaxEntries) { 214 *error_msg = android::base::StringPrintf("Requested size exceeds maximum: %zu", new_size); 215 return false; 216 } 217 // Note: the above check also ensures that there is no overflow below. 218 219 const size_t table_bytes = new_size * sizeof(IrtEntry); 220 std::unique_ptr<MemMap> new_map(MemMap::MapAnonymous("indirect ref table", 221 nullptr, 222 table_bytes, 223 PROT_READ | PROT_WRITE, 224 false, 225 false, 226 error_msg)); 227 if (new_map == nullptr) { 228 return false; 229 } 230 231 memcpy(new_map->Begin(), table_mem_map_->Begin(), table_mem_map_->Size()); 232 table_mem_map_ = std::move(new_map); 233 table_ = reinterpret_cast<IrtEntry*>(table_mem_map_->Begin()); 234 max_entries_ = new_size; 235 236 return true; 237 } 238 239 IndirectRef IndirectReferenceTable::Add(IRTSegmentState previous_state, 240 ObjPtr<mirror::Object> obj) { 241 if (kDebugIRT) { 242 LOG(INFO) << "+++ Add: previous_state=" << previous_state.top_index 243 << " top_index=" << segment_state_.top_index 244 << " last_known_prev_top_index=" << last_known_previous_state_.top_index 245 << " holes=" << current_num_holes_; 246 } 247 248 size_t top_index = segment_state_.top_index; 249 250 CHECK(obj != nullptr); 251 VerifyObject(obj); 252 DCHECK(table_ != nullptr); 253 254 if (top_index == max_entries_) { 255 if (resizable_ == ResizableCapacity::kNo) { 256 LOG(FATAL) << "JNI ERROR (app bug): " << kind_ << " table overflow " 257 << "(max=" << max_entries_ << ")\n" 258 << MutatorLockedDumpable<IndirectReferenceTable>(*this); 259 UNREACHABLE(); 260 } 261 262 // Try to double space. 263 if (std::numeric_limits<size_t>::max() / 2 < max_entries_) { 264 LOG(FATAL) << "JNI ERROR (app bug): " << kind_ << " table overflow " 265 << "(max=" << max_entries_ << ")" << std::endl 266 << MutatorLockedDumpable<IndirectReferenceTable>(*this) 267 << " Resizing failed: exceeds size_t"; 268 UNREACHABLE(); 269 } 270 271 std::string error_msg; 272 if (!Resize(max_entries_ * 2, &error_msg)) { 273 LOG(FATAL) << "JNI ERROR (app bug): " << kind_ << " table overflow " 274 << "(max=" << max_entries_ << ")" << std::endl 275 << MutatorLockedDumpable<IndirectReferenceTable>(*this) 276 << " Resizing failed: " << error_msg; 277 UNREACHABLE(); 278 } 279 } 280 281 RecoverHoles(previous_state); 282 CheckHoleCount(table_, current_num_holes_, previous_state, segment_state_); 283 284 // We know there's enough room in the table. Now we just need to find 285 // the right spot. If there's a hole, find it and fill it; otherwise, 286 // add to the end of the list. 287 IndirectRef result; 288 size_t index; 289 if (current_num_holes_ > 0) { 290 DCHECK_GT(top_index, 1U); 291 // Find the first hole; likely to be near the end of the list. 292 IrtEntry* p_scan = &table_[top_index - 1]; 293 DCHECK(!p_scan->GetReference()->IsNull()); 294 --p_scan; 295 while (!p_scan->GetReference()->IsNull()) { 296 DCHECK_GE(p_scan, table_ + previous_state.top_index); 297 --p_scan; 298 } 299 index = p_scan - table_; 300 current_num_holes_--; 301 } else { 302 // Add to the end. 303 index = top_index++; 304 segment_state_.top_index = top_index; 305 } 306 table_[index].Add(obj); 307 result = ToIndirectRef(index); 308 if (kDebugIRT) { 309 LOG(INFO) << "+++ added at " << ExtractIndex(result) << " top=" << segment_state_.top_index 310 << " holes=" << current_num_holes_; 311 } 312 313 DCHECK(result != nullptr); 314 return result; 315 } 316 317 void IndirectReferenceTable::AssertEmpty() { 318 for (size_t i = 0; i < Capacity(); ++i) { 319 if (!table_[i].GetReference()->IsNull()) { 320 LOG(FATAL) << "Internal Error: non-empty local reference table\n" 321 << MutatorLockedDumpable<IndirectReferenceTable>(*this); 322 UNREACHABLE(); 323 } 324 } 325 } 326 327 // Removes an object. We extract the table offset bits from "iref" 328 // and zap the corresponding entry, leaving a hole if it's not at the top. 329 // If the entry is not between the current top index and the bottom index 330 // specified by the cookie, we don't remove anything. This is the behavior 331 // required by JNI's DeleteLocalRef function. 332 // This method is not called when a local frame is popped; this is only used 333 // for explicit single removals. 334 // Returns "false" if nothing was removed. 335 bool IndirectReferenceTable::Remove(IRTSegmentState previous_state, IndirectRef iref) { 336 if (kDebugIRT) { 337 LOG(INFO) << "+++ Remove: previous_state=" << previous_state.top_index 338 << " top_index=" << segment_state_.top_index 339 << " last_known_prev_top_index=" << last_known_previous_state_.top_index 340 << " holes=" << current_num_holes_; 341 } 342 343 const uint32_t top_index = segment_state_.top_index; 344 const uint32_t bottom_index = previous_state.top_index; 345 346 DCHECK(table_ != nullptr); 347 348 if (GetIndirectRefKind(iref) == kHandleScopeOrInvalid) { 349 auto* self = Thread::Current(); 350 if (self->HandleScopeContains(reinterpret_cast<jobject>(iref))) { 351 auto* env = self->GetJniEnv(); 352 DCHECK(env != nullptr); 353 if (env->check_jni) { 354 ScopedObjectAccess soa(self); 355 LOG(WARNING) << "Attempt to remove non-JNI local reference, dumping thread"; 356 if (kDumpStackOnNonLocalReference) { 357 self->Dump(LOG_STREAM(WARNING)); 358 } 359 } 360 return true; 361 } 362 } 363 const uint32_t idx = ExtractIndex(iref); 364 if (idx < bottom_index) { 365 // Wrong segment. 366 LOG(WARNING) << "Attempt to remove index outside index area (" << idx 367 << " vs " << bottom_index << "-" << top_index << ")"; 368 return false; 369 } 370 if (idx >= top_index) { 371 // Bad --- stale reference? 372 LOG(WARNING) << "Attempt to remove invalid index " << idx 373 << " (bottom=" << bottom_index << " top=" << top_index << ")"; 374 return false; 375 } 376 377 RecoverHoles(previous_state); 378 CheckHoleCount(table_, current_num_holes_, previous_state, segment_state_); 379 380 if (idx == top_index - 1) { 381 // Top-most entry. Scan up and consume holes. 382 383 if (!CheckEntry("remove", iref, idx)) { 384 return false; 385 } 386 387 *table_[idx].GetReference() = GcRoot<mirror::Object>(nullptr); 388 if (current_num_holes_ != 0) { 389 uint32_t collapse_top_index = top_index; 390 while (--collapse_top_index > bottom_index && current_num_holes_ != 0) { 391 if (kDebugIRT) { 392 ScopedObjectAccess soa(Thread::Current()); 393 LOG(INFO) << "+++ checking for hole at " << collapse_top_index - 1 394 << " (previous_state=" << bottom_index << ") val=" 395 << table_[collapse_top_index - 1].GetReference()->Read<kWithoutReadBarrier>(); 396 } 397 if (!table_[collapse_top_index - 1].GetReference()->IsNull()) { 398 break; 399 } 400 if (kDebugIRT) { 401 LOG(INFO) << "+++ ate hole at " << (collapse_top_index - 1); 402 } 403 current_num_holes_--; 404 } 405 segment_state_.top_index = collapse_top_index; 406 407 CheckHoleCount(table_, current_num_holes_, previous_state, segment_state_); 408 } else { 409 segment_state_.top_index = top_index - 1; 410 if (kDebugIRT) { 411 LOG(INFO) << "+++ ate last entry " << top_index - 1; 412 } 413 } 414 } else { 415 // Not the top-most entry. This creates a hole. We null out the entry to prevent somebody 416 // from deleting it twice and screwing up the hole count. 417 if (table_[idx].GetReference()->IsNull()) { 418 LOG(INFO) << "--- WEIRD: removing null entry " << idx; 419 return false; 420 } 421 if (!CheckEntry("remove", iref, idx)) { 422 return false; 423 } 424 425 *table_[idx].GetReference() = GcRoot<mirror::Object>(nullptr); 426 current_num_holes_++; 427 CheckHoleCount(table_, current_num_holes_, previous_state, segment_state_); 428 if (kDebugIRT) { 429 LOG(INFO) << "+++ left hole at " << idx << ", holes=" << current_num_holes_; 430 } 431 } 432 433 return true; 434 } 435 436 void IndirectReferenceTable::Trim() { 437 ScopedTrace trace(__PRETTY_FUNCTION__); 438 const size_t top_index = Capacity(); 439 auto* release_start = AlignUp(reinterpret_cast<uint8_t*>(&table_[top_index]), kPageSize); 440 uint8_t* release_end = table_mem_map_->End(); 441 madvise(release_start, release_end - release_start, MADV_DONTNEED); 442 } 443 444 void IndirectReferenceTable::VisitRoots(RootVisitor* visitor, const RootInfo& root_info) { 445 BufferedRootVisitor<kDefaultBufferedRootCount> root_visitor(visitor, root_info); 446 for (auto ref : *this) { 447 if (!ref->IsNull()) { 448 root_visitor.VisitRoot(*ref); 449 DCHECK(!ref->IsNull()); 450 } 451 } 452 } 453 454 void IndirectReferenceTable::Dump(std::ostream& os) const { 455 os << kind_ << " table dump:\n"; 456 ReferenceTable::Table entries; 457 for (size_t i = 0; i < Capacity(); ++i) { 458 ObjPtr<mirror::Object> obj = table_[i].GetReference()->Read<kWithoutReadBarrier>(); 459 if (obj != nullptr) { 460 obj = table_[i].GetReference()->Read(); 461 entries.push_back(GcRoot<mirror::Object>(obj)); 462 } 463 } 464 ReferenceTable::Dump(os, entries); 465 } 466 467 void IndirectReferenceTable::SetSegmentState(IRTSegmentState new_state) { 468 if (kDebugIRT) { 469 LOG(INFO) << "Setting segment state: " 470 << segment_state_.top_index 471 << " -> " 472 << new_state.top_index; 473 } 474 segment_state_ = new_state; 475 } 476 477 bool IndirectReferenceTable::EnsureFreeCapacity(size_t free_capacity, std::string* error_msg) { 478 size_t top_index = segment_state_.top_index; 479 if (top_index < max_entries_ && top_index + free_capacity <= max_entries_) { 480 return true; 481 } 482 483 // We're only gonna do a simple best-effort here, ensuring the asked-for capacity at the end. 484 if (resizable_ == ResizableCapacity::kNo) { 485 *error_msg = "Table is not resizable"; 486 return false; 487 } 488 489 // Try to increase the table size. 490 491 // Would this overflow? 492 if (std::numeric_limits<size_t>::max() - free_capacity < top_index) { 493 *error_msg = "Cannot resize table, overflow."; 494 return false; 495 } 496 497 if (!Resize(top_index + free_capacity, error_msg)) { 498 LOG(WARNING) << "JNI ERROR: Unable to reserve space in EnsureFreeCapacity (" << free_capacity 499 << "): " << std::endl 500 << MutatorLockedDumpable<IndirectReferenceTable>(*this) 501 << " Resizing failed: " << *error_msg; 502 return false; 503 } 504 return true; 505 } 506 507 size_t IndirectReferenceTable::FreeCapacity() { 508 return max_entries_ - segment_state_.top_index; 509 } 510 511 } // namespace art 512