in cachelib/compact_cache/CCacheVariableLruBucket.h [767:879]
static bool evictEntries(Bucket* bucket,
size_t requiredSpace,
EvictionCb evictionCb) {
/* Will contain all the entries we decide to evict. */
std::vector<EntryHdr*> arr;
size_t freeSpace = kBucketDataSize - bucket->totalDataSize -
sizeof(EntryHdr) * bucket->numEntries;
if (freeSpace >= requiredSpace && bucket->numEntries != kMaxEntries) {
/* We already have enough space. */
return false;
}
/* 1) Walk through the EntryHdr headers starting from the LRU while
* updating a counter that contains the memory made available if
* evicted all entries seen so far. Stop when this counter is high
* enough (i.e bigger than requiredSpace). */
/* Start from the lru, which is the last entry in the entry header. */
unsigned int evictedPos = bucket->numEntries - 1;
/* Convenient lambda function for evicting an entry. */
auto evictOneMoreEntryFn = [&]() {
EntryHdr* entry = getEntryHeader(bucket, evictedPos);
/* There should always be at least one entry for eviction until
* we have enough space. */
XDCHECK_GE(reinterpret_cast<uintptr_t>(entry),
reinterpret_cast<uintptr_t>(getEntryHeader(bucket, 0)));
/* Evicting the entry releases the space of the entry data and the
* space of the entry header. */
freeSpace += entry->dataSize + sizeof(EntryHdr) + sizeof(EntryData);
arr.push_back(entry);
evictionCb(EntryHandle(bucket, evictedPos));
evictedPos--;
};
/* Evict at least one entry if the current number of entries is about to
* overflow. This should not happen very often.
* If this happens often, this means that the bucket is too big for the
* entries, and we are wasting a lot of memory. */
if (bucket->numEntries == kMaxEntries) {
XLOG(ERR) << "Overflow in number of entries in a bucket";
evictOneMoreEntryFn();
}
/* Evict entries until we have enough space. */
while (freeSpace < requiredSpace) {
evictOneMoreEntryFn();
}
/* 2) Sort the list of entries we decided to evict by their offset in
* the "Data" section, in increasing order, so that the left-most
* evicted entry is the first element of the array, and the right-most
* evected entry is the last element.
* The cost of sorting the evicted entries should be negligible since
* the number of evicted entries should be small. */
auto compareFn = [](const EntryHdr* a, const EntryHdr* b) -> bool {
return a->dataOffset < b->dataOffset;
};
XDCHECK_GT(arr.size(), 0);
std::sort(arr.begin(), arr.end(), compareFn);
/* 3) Move the "chunks" of EntryData objects that are between two
* evicted entries, one by one. */
size_t shiftDistance = 0;
EntryDataOffset chunkStartOffset;
int i = 0;
for (i = arr.size() - 1; i >= 0; i--) {
/* Amount of bytes by which to shift the chunk. We are removing the
* current entry 'arr[i]', so we shift by the total amount of bytes
* used by its corresponding EntryData. Here, we increment
* shiftDistance instead of simply setting it to a new value because
* we want to take into account the space made available by the
* shifting performed by the previous iterations of this loop. */
shiftDistance += arr[i]->dataSize + sizeof(EntryData);
/* Compute the start offset of the chunk we are moving.
* The chunk starts right at the end of the removed entry that is
* at the left of the current removed entry. If the current removed
* entry is the left-most, the start offset of the chunk is the
* beginning of the data. */
if (i == 0) {
chunkStartOffset = getFirstEntryDataOffset(bucket);
} else {
chunkStartOffset =
arr[i - 1]->dataOffset + arr[i - 1]->dataSize + sizeof(EntryData);
}
/* Size of the chunk to be moved. */
size_t shiftedChunkSize = arr[i]->dataOffset - chunkStartOffset;
if (shiftedChunkSize == 0) {
/* The current removed entry is contiguous with the removed
* entry on the left, so there is nothing between them to be
* moved. */
continue;
}
/* Pointer to the beginning of that chunk. */
EntryData* src =
reinterpret_cast<EntryData*>(bucket->data + chunkStartOffset);
shiftEntriesData(bucket, src, shiftDistance, shiftedChunkSize);
}
/* 4) reduce the number of entries and the total size of the entries in
* the bucket. */
XDCHECK_GE(bucket->numEntries, arr.size());
XDCHECK_GE(bucket->totalDataSize, shiftDistance);
bucket->numEntries -= arr.size();
bucket->totalDataSize -= shiftDistance;
return true;
}