[scudo] Secondary release to OS uses LRU to scan. (#163691)
Before this change, the code would scan the entire set of cached entries
to find ones to be released. Now, it uses the LRUEntries list to iterate
over the live cached entries. In addition, remove the OldestTime
variable and replace it with OldestPresentEntry which will always be the
oldest entry in the LRU that has Time non-zero.
diff --git a/compiler-rt/lib/scudo/standalone/secondary.h b/compiler-rt/lib/scudo/standalone/secondary.h
index f0b7bce..2509db2 100644
--- a/compiler-rt/lib/scudo/standalone/secondary.h
+++ b/compiler-rt/lib/scudo/standalone/secondary.h
@@ -249,6 +249,7 @@
LRUEntries.clear();
LRUEntries.init(Entries, sizeof(Entries));
+ OldestPresentEntry = nullptr;
AvailEntries.clear();
AvailEntries.init(Entries, sizeof(Entries));
@@ -322,8 +323,6 @@
}
CachedBlock PrevEntry = Quarantine[QuarantinePos];
Quarantine[QuarantinePos] = Entry;
- if (OldestTime == 0)
- OldestTime = Entry.Time;
Entry = PrevEntry;
}
@@ -339,9 +338,6 @@
}
insert(Entry);
-
- if (OldestTime == 0)
- OldestTime = Entry.Time;
} while (0);
for (MemMapT &EvictMemMap : EvictionMemMaps)
@@ -355,7 +351,6 @@
SCUDO_SCOPED_TRACE(
GetSecondaryReleaseToOSTraceName(ReleaseToOS::Normal));
- // TODO: Add ReleaseToOS logic to LRU algorithm
releaseOlderThan(Time - static_cast<u64>(Interval) * 1000000);
Mutex.unlock();
} else
@@ -535,6 +530,11 @@
void unmapTestOnly() { empty(); }
+ void releaseOlderThanTestOnly(u64 ReleaseTime) {
+ ScopedLock L(Mutex);
+ releaseOlderThan(ReleaseTime);
+ }
+
private:
void insert(const CachedBlock &Entry) REQUIRES(Mutex) {
CachedBlock *AvailEntry = AvailEntries.front();
@@ -542,10 +542,16 @@
*AvailEntry = Entry;
LRUEntries.push_front(AvailEntry);
+ if (OldestPresentEntry == nullptr && AvailEntry->Time != 0)
+ OldestPresentEntry = AvailEntry;
}
void remove(CachedBlock *Entry) REQUIRES(Mutex) {
DCHECK(Entry->isValid());
+ if (OldestPresentEntry == Entry) {
+ OldestPresentEntry = LRUEntries.getPrev(Entry);
+ DCHECK(OldestPresentEntry == nullptr || OldestPresentEntry->Time != 0);
+ }
LRUEntries.remove(Entry);
Entry->invalidate();
AvailEntries.push_front(Entry);
@@ -560,6 +566,7 @@
for (CachedBlock &Entry : LRUEntries)
MapInfo[N++] = Entry.MemMap;
LRUEntries.clear();
+ OldestPresentEntry = nullptr;
}
for (uptr I = 0; I < N; I++) {
MemMapT &MemMap = MapInfo[I];
@@ -567,36 +574,42 @@
}
}
- void releaseIfOlderThan(CachedBlock &Entry, u64 Time) REQUIRES(Mutex) {
- if (!Entry.isValid() || !Entry.Time)
- return;
- if (Entry.Time > Time) {
- if (OldestTime == 0 || Entry.Time < OldestTime)
- OldestTime = Entry.Time;
- return;
- }
- Entry.MemMap.releaseAndZeroPagesToOS(Entry.CommitBase, Entry.CommitSize);
- Entry.Time = 0;
- }
-
- void releaseOlderThan(u64 Time) REQUIRES(Mutex) {
+ void releaseOlderThan(u64 ReleaseTime) REQUIRES(Mutex) {
SCUDO_SCOPED_TRACE(GetSecondaryReleaseOlderThanTraceName());
- if (!LRUEntries.size() || OldestTime == 0 || OldestTime > Time)
- return;
- OldestTime = 0;
- if (!Config::getQuarantineDisabled())
- for (uptr I = 0; I < Config::getQuarantineSize(); I++)
- releaseIfOlderThan(Quarantine[I], Time);
- for (uptr I = 0; I < Config::getEntriesArraySize(); I++)
- releaseIfOlderThan(Entries[I], Time);
+ if (!Config::getQuarantineDisabled()) {
+ for (uptr I = 0; I < Config::getQuarantineSize(); I++) {
+ auto &Entry = Quarantine[I];
+ if (!Entry.isValid() || Entry.Time == 0 || Entry.Time > ReleaseTime)
+ continue;
+ Entry.MemMap.releaseAndZeroPagesToOS(Entry.CommitBase,
+ Entry.CommitSize);
+ Entry.Time = 0;
+ }
+ }
+
+ for (CachedBlock *Entry = OldestPresentEntry; Entry != nullptr;
+ Entry = LRUEntries.getPrev(Entry)) {
+ DCHECK(Entry->isValid());
+ DCHECK(Entry->Time != 0);
+
+ if (Entry->Time > ReleaseTime) {
+ // All entries are newer than this, so no need to keep scanning.
+ OldestPresentEntry = Entry;
+ return;
+ }
+
+ Entry->MemMap.releaseAndZeroPagesToOS(Entry->CommitBase,
+ Entry->CommitSize);
+ Entry->Time = 0;
+ }
+ OldestPresentEntry = nullptr;
}
HybridMutex Mutex;
u32 QuarantinePos GUARDED_BY(Mutex) = 0;
atomic_u32 MaxEntriesCount = {};
atomic_uptr MaxEntrySize = {};
- u64 OldestTime GUARDED_BY(Mutex) = 0;
atomic_s32 ReleaseToOsIntervalMs = {};
u32 CallsToRetrieve GUARDED_BY(Mutex) = 0;
u32 SuccessfulRetrieves GUARDED_BY(Mutex) = 0;
@@ -606,6 +619,8 @@
NonZeroLengthArray<CachedBlock, Config::getQuarantineSize()>
Quarantine GUARDED_BY(Mutex) = {};
+ // The oldest entry in the LRUEntries that has Time non-zero.
+ CachedBlock *OldestPresentEntry GUARDED_BY(Mutex) = nullptr;
// Cached blocks stored in LRU order
DoublyLinkedList<CachedBlock> LRUEntries GUARDED_BY(Mutex);
// The unused Entries
diff --git a/compiler-rt/lib/scudo/standalone/tests/secondary_test.cpp b/compiler-rt/lib/scudo/standalone/tests/secondary_test.cpp
index d8a7f6b..855a3e6 100644
--- a/compiler-rt/lib/scudo/standalone/tests/secondary_test.cpp
+++ b/compiler-rt/lib/scudo/standalone/tests/secondary_test.cpp
@@ -403,6 +403,11 @@
MemMap.getBase(), MemMap);
}
}
+
+ void storeMemMap(scudo::MemMapT &MemMap) {
+ Cache->store(Options, MemMap.getBase(), MemMap.getCapacity(),
+ MemMap.getBase(), MemMap);
+ }
};
TEST(ScudoSecondaryTest, AllocatorCacheEntryOrder) {
@@ -503,3 +508,83 @@
Info.Cache->setOption(scudo::Option::MaxCacheEntrySize, 1UL << 20));
EXPECT_TRUE(Info.Cache->canCache(1UL << 16));
}
+
+TEST(ScudoSecondaryTest, ReleaseOlderThanAllEntries) {
+ CacheInfoType<TestCacheConfig> Info;
+ using CacheConfig = CacheInfoType<TestCacheConfig>::CacheConfig;
+
+ Info.Cache->releaseOlderThanTestOnly(UINT64_MAX);
+
+ Info.fillCacheWithSameSizeBlocks(CacheConfig::getDefaultMaxEntriesCount(),
+ 1024);
+ for (size_t I = 0; I < Info.MemMaps.size(); I++) {
+ // Set the first u32 value to a non-zero value.
+ *reinterpret_cast<scudo::u32 *>(Info.MemMaps[I].getBase()) = 10;
+ }
+
+ Info.Cache->releaseOlderThanTestOnly(UINT64_MAX);
+
+ EXPECT_EQ(Info.MemMaps.size(), CacheConfig::getDefaultMaxEntriesCount());
+ for (size_t I = 0; I < Info.MemMaps.size(); I++) {
+ // All released maps will now be zero.
+ EXPECT_EQ(*reinterpret_cast<scudo::u32 *>(Info.MemMaps[I].getBase()), 0U);
+ }
+}
+
+// This test assumes that the timestamp comes from getMonotonicFast.
+TEST(ScudoSecondaryTest, ReleaseOlderThanGroups) {
+ CacheInfoType<TestCacheConfig> Info;
+
+ // Disable the release interval so we can do tests the releaseOlderThan
+ // function.
+ Info.Cache->setOption(scudo::Option::ReleaseInterval, -1);
+
+ // Create all of the maps we are going to use.
+ for (size_t I = 0; I < 6; I++) {
+ Info.MemMaps.emplace_back(Info.allocate(1024));
+ // Set the first u32 value to a non-zero value.
+ *reinterpret_cast<scudo::u32 *>(Info.MemMaps[I].getBase()) = 10;
+ }
+
+ // Create three groups of entries at three different intervals.
+ Info.storeMemMap(Info.MemMaps[0]);
+ Info.storeMemMap(Info.MemMaps[1]);
+ scudo::u64 FirstTime = scudo::getMonotonicTimeFast();
+
+ // Need to make sure the next set of entries are stamped with a newer time.
+ while (scudo::getMonotonicTimeFast() <= FirstTime)
+ ;
+
+ Info.storeMemMap(Info.MemMaps[2]);
+ Info.storeMemMap(Info.MemMaps[3]);
+ scudo::u64 SecondTime = scudo::getMonotonicTimeFast();
+
+ // Need to make sure the next set of entries are stamped with a newer time.
+ while (scudo::getMonotonicTimeFast() <= SecondTime)
+ ;
+
+ Info.storeMemMap(Info.MemMaps[4]);
+ Info.storeMemMap(Info.MemMaps[5]);
+ scudo::u64 ThirdTime = scudo::getMonotonicTimeFast();
+
+ Info.Cache->releaseOlderThanTestOnly(FirstTime);
+ for (size_t I = 0; I < 2; I++) {
+ EXPECT_EQ(*reinterpret_cast<scudo::u32 *>(Info.MemMaps[I].getBase()), 0U);
+ }
+ for (size_t I = 2; I < 6; I++) {
+ EXPECT_EQ(*reinterpret_cast<scudo::u32 *>(Info.MemMaps[I].getBase()), 10U);
+ }
+
+ Info.Cache->releaseOlderThanTestOnly(SecondTime);
+ for (size_t I = 0; I < 4; I++) {
+ EXPECT_EQ(*reinterpret_cast<scudo::u32 *>(Info.MemMaps[I].getBase()), 0U);
+ }
+ for (size_t I = 4; I < 6; I++) {
+ EXPECT_EQ(*reinterpret_cast<scudo::u32 *>(Info.MemMaps[I].getBase()), 10U);
+ }
+
+ Info.Cache->releaseOlderThanTestOnly(ThirdTime);
+ for (size_t I = 0; I < 6; I++) {
+ EXPECT_EQ(*reinterpret_cast<scudo::u32 *>(Info.MemMaps[I].getBase()), 0U);
+ }
+}
