Loading...
--- dyld/dyld-1122.1/cache_builder/IMPCaches.cpp
+++ dyld/dyld-1330/cache_builder/IMPCaches.cpp
@@ -343,52 +343,35 @@
}
}
-int AddressSpace::sizeAvailableAfterIndex(int idx) const
-{
- int availableAfterThisAddress = bagSizeAtIndex(idx) - sizeAtIndex(idx);
+// Returns the size of the unbroken chain of empty cells
+// after idx to the space remaining in cell idx.
+// This is used to see if there is space to let a very
+// long method name overflow into the following empty cells.
+int AddressSpace::sizeAvailableAtOrAfterIndex(int idx) const
+{
+ int availableAtOrAfterThisIndex = bagSizeAtIndex(idx) - sizeAtIndex(idx);
+ if (availableAtOrAfterThisIndex == 0) return 0;
+
for (int j = idx + 1; j < maximumIndex; j++) {
- if (methodsByIndex.find(j) != methodsByIndex.end()) {
+ if (sizeAtIndex(j) > 0) {
break;
} else {
- availableAfterThisAddress += bagSizeAtIndex(j);
- }
- }
-
- return availableAfterThisAddress;
-}
-
-// Because some selectors are longer than 128 bytes, we have to sometimes let
-// them overflow into the next 128-byte bucket. This method tells you if you
-// can place a method in a bucket without colliding with an overflowing selector
-// from one of the previous buckets.
-bool AddressSpace::canPlaceWithoutFillingOverflowCellAtIndex(int idx) const
-{
- if ((idx == 0) || (sizeAtIndex(idx) > 0)) {
- return true;
- }
-
- int j = idx;
- int availableOnOrBefore = 0;
-
- while (j > 0 && (sizeAtIndex(j) == 0)) {
- availableOnOrBefore += bagSizeAtIndex(j);
- j -= 1;
- }
-
- int sizeOfFirstNonEmptyCellBefore = sizeAtIndex(j);
- return (sizeOfFirstNonEmptyCellBefore < availableOnOrBefore);
+ availableAtOrAfterThisIndex += bagSizeAtIndex(j);
+ }
+ }
+
+ return availableAtOrAfterThisIndex;
}
bool AddressSpace::canPlaceMethodAtIndex(const Selector* method, int idx) const
{
- int existingSize = sizeAtIndex(idx);
- bool canPlaceWithoutFillingOverflow = canPlaceWithoutFillingOverflowCellAtIndex(idx);
-
- if (!canPlaceWithoutFillingOverflow) {
+ int existingSize = sizeAtIndex(idx);
+ int available = bagSizeAtIndex(idx) - existingSize;
+
+ if (available == 0) {
return false;
}
- int available = bagSizeAtIndex(idx) - existingSize;
int methodSize = method->size();
bool enoughRoom = available > methodSize;
@@ -396,18 +379,51 @@
return true;
}
- bool tooBigButOverflowExists = (methodSize > 64) && (available > 0) && (sizeAvailableAfterIndex(idx) > methodSize);
+ // For long selectors (more than 64 characters), we let them overflow into the next cells
+ // if they are still empty. Otherwise they are very difficult to place.
+ bool tooBigButOverflowExists = (methodSize > 64) && (sizeAvailableAtOrAfterIndex(idx) >= methodSize);
return tooBigButOverflowExists;
}
void AddressSpace::placeMethodAtIndex(Selector* method, int idx)
{
- auto [it, success] = methodsByIndex.try_emplace(idx, std::vector<Selector*>());
- it->second.push_back(method);
-
- auto [it2, success2] = sizes.try_emplace(idx, 0);
- it2->second += method->size();
+ auto [methods_it, success] = methodsByIndex.try_emplace(idx, std::vector<Selector*>());
+ methods_it->second.push_back(method);
+
+ auto [sizes_it, success2] = sizes.try_emplace(idx, 0);
+ int remainingToPlace = method->size();
+
+ int bagSize = bagSizeAtIndex(idx);
+ const int occupiedInThisBag = sizes_it->second;
+ const int availableInThisBag = bagSize - occupiedInThisBag;
+
+ // If we can place the method now, do it and return
+ if (availableInThisBag >= remainingToPlace) {
+ sizes_it->second += remainingToPlace;
+ return;
+ }
+
+ // Otherwise we have to deal with overflows:
+ // Go through the next cells (which are supposed to be empty at this point, see
+ // canPlaceMethodAtIndex) and adjust their sizes until we have placed all
+ // of the characters in the method name.
+ sizes_it->second = bagSize;
+ remainingToPlace -= availableInThisBag;
+
+ while (remainingToPlace > 0) {
+ idx++;
+ std::tie(sizes_it, success2) = sizes.try_emplace(idx, 0);
+ bagSize = bagSizeAtIndex(idx);
+
+ // If there was no room for overflow canPlaceMethodAtIndex should have denied this
+ assert(sizes_it->second == 0);
+
+ int sizeToAdd = std::min(bagSize, remainingToPlace);
+ sizes_it->second = sizeToAdd;
+
+ remainingToPlace -= sizeToAdd;
+ }
}
// At this point selected are already sorted into 128-byte buckets.
@@ -730,7 +746,7 @@
(trackedArray.find(classNameStr) != trackedArray.end());
}
-void IMPCachesBuilder::addMethod(IMPCaches::ClassData* classDataPtr, std::string_view methodName, std::string_view installName, std::string_view className, std::string_view catName, bool inlined, bool fromFlattening) {
+bool IMPCachesBuilder::addMethod(IMPCaches::ClassData* classDataPtr, std::string_view methodName, std::string_view installName, std::string_view className, std::string_view catName, bool inlined, bool fromFlattening) {
std::string_view methodNameView(methodName);
auto [selectorIterator, success] = selectors.map.try_emplace(methodNameView, std::make_unique<Selector>());
@@ -763,6 +779,8 @@
thisSelectorData->classes.push_back(classDataPtr);
classDataPtr->methods.push_back(m);
}
+
+ return !exists;
}
void IMPCachesBuilder::inlineMethodIfNeeded(IMPCaches::ClassData* classToInlineIn, std::string_view classToInlineFrom, std::string_view catToInlineFrom, std::string_view installNameToInlineFrom, std::string_view name, std::set<Selector*>& seenSelectors, bool isFlattening) {
@@ -869,10 +887,13 @@
thisData->isMetaclass = theClass.isMetaClass;
thisData->shouldGenerateImpCache = interesting;
+ bool duplicateMethod = false;
for ( const imp_caches::Method& objcMethod : objcClass.methods ) {
const bool inlined = false;
const bool fromFlattening = false;
- addMethod(thisDataPtr, objcMethod.name, dylib.inputDylib->installName, theClass.className, "", inlined, fromFlattening);
+ bool added = addMethod(thisDataPtr, objcMethod.name, dylib.inputDylib->installName, theClass.className, "", inlined, fromFlattening);
+ if ( !added )
+ duplicateMethod = true;
}
ClassKey key {
@@ -881,7 +902,7 @@
};
assert(dylib.impCachesClassData.find(key) == dylib.impCachesClassData.end());
- if (duplicateClasses.find(key) != duplicateClasses.end()) {
+ if (duplicateMethod || (duplicateClasses.find(key) != duplicateClasses.end()) ) {
// We can't just set shouldGenerateImpCache to false ; we do it later
// when we have built the flattening hierarchies in order to drop
// any related classes as well.
@@ -1120,9 +1141,36 @@
for (const auto& [k,v] : selectors.map) {
totalSize += v->size();
}
- if (totalSize >= (1 << 24)) {
- diag.warning("Dropping all IMP caches ; too many selectors\n");
- return false;
+
+ // Allow up to 75% of total space
+ const uint64_t maxSelectors = selectorSizeLimit * 0.75;
+
+ if (totalSize >= maxSelectors) {
+ diag.warning("Dropping some IMP caches ; too many selectors\n");
+
+ // Get a sorted list of classes, to match what we do later in findShiftsAndMasks()
+ std::vector<IMPCaches::ClassData*> allClasses;
+ fillAllClasses(allClasses);
+
+ // Walk all the methods in order, assuming they are prioritised. When we hit 75% of selector space, stop
+ // allowing new selectors, and so stop allowing new classes which would need more selectors
+ uint64_t selectorsSize = magicSelector.size() + 1;
+ std::unordered_set<std::string_view> seenSelectors;
+
+ for ( IMPCaches::ClassData* classData : allClasses) {
+ for ( const ClassData::Method& method : classData->methods ) {
+ if ( seenSelectors.count(method.selector->name) )
+ continue;
+
+ if ( (selectorsSize + method.selector->name.size() + 1) > maxSelectors ) {
+ classData->shouldGenerateImpCache = false;
+ break;
+ }
+
+ seenSelectors.insert(method.selector->name);
+ selectorsSize += method.selector->name.size() + 1;
+ }
+ }
}
for (DylibState& d : dylibs) {
@@ -1256,21 +1304,22 @@
}
}
-const std::string * IMPCachesBuilder::nameAndIsMetaclassPairFromNode(const dyld3::json::Node & node, bool* metaclass) {
- const dyld3::json::Node& metaclassNode = dyld3::json::getRequiredValue(_diagnostics, node, "metaclass");
+const std::string * IMPCachesBuilder::nameAndIsMetaclassPairFromNode(const json::Node & node, bool* metaclass) {
+ const json::Node& metaclassNode = json::getRequiredValue(_diagnostics, node, "metaclass");
if (_diagnostics.hasError()) return nullptr;
- if (metaclass != nullptr) *metaclass = dyld3::json::parseRequiredInt(_diagnostics, metaclassNode) != 0;
- const dyld3::json::Node& nameNode = dyld3::json::getRequiredValue(_diagnostics, node, "name");
+ if (metaclass != nullptr) *metaclass = json::parseRequiredInt(_diagnostics, metaclassNode) != 0;
+ const json::Node& nameNode = json::getRequiredValue(_diagnostics, node, "name");
if (_diagnostics.hasError()) return nullptr;
- return &(dyld3::json::parseRequiredString(_diagnostics, nameNode));
+ return &(json::parseRequiredString(_diagnostics, nameNode));
}
IMPCachesBuilder::IMPCachesBuilder(Diagnostics& diag, TimeRecorder& timeRecorder,
const std::vector<imp_caches::Dylib>& inputDylibs,
- const dyld3::json::Node& optimizerConfiguration)
- : _diagnostics(diag), _timeRecorder(timeRecorder)
+ const json::Node& optimizerConfiguration,
+ uint32_t selectorSizeLimit)
+ : selectorSizeLimit(selectorSizeLimit), _diagnostics(diag), _timeRecorder(timeRecorder)
{
// Add one DylibState for every input dylib
this->dylibs.reserve(inputDylibs.size());
@@ -1280,19 +1329,19 @@
this->dylibs.push_back(std::move(d));
}
- const dyld3::json::Node * version = dyld3::json::getOptionalValue(diag, optimizerConfiguration, "version");
- int64_t versionInt = (version != NULL) ? dyld3::json::parseRequiredInt(diag, *version) : 1;
+ const json::Node * version = json::getOptionalValue(diag, optimizerConfiguration, "version");
+ int64_t versionInt = (version != NULL) ? json::parseRequiredInt(diag, *version) : 1;
if (versionInt == 2) {
// v2 has a single neededClasses array, with a key to know if it's a metaclass
// or class. This lets us order them by importance so that we handle the important
// cases first in the algorithm, while it's still easy to place things (as we process
// more classes, constraints build up and we risk dropping difficult classes)
- const dyld3::json::Node& classes = dyld3::json::getRequiredValue(diag, optimizerConfiguration, "neededClasses");
+ const json::Node& classes = json::getRequiredValue(diag, optimizerConfiguration, "neededClasses");
if (diag.hasError()) return;
int i = 0;
- for (const dyld3::json::Node& n : classes.array) {
+ for (const json::Node& n : classes.array) {
bool metaclass = false;
const std::string *name = nameAndIsMetaclassPairFromNode(n, &metaclass);
if (name != nullptr) {
@@ -1311,7 +1360,7 @@
int i = 0;
if (metaclasses != optimizerConfiguration.map.cend()) {
- for (const dyld3::json::Node& n : metaclasses->second.array) {
+ for (const json::Node& n : metaclasses->second.array) {
neededMetaclasses[n.value] = i++;
}
}
@@ -1319,7 +1368,7 @@
auto classes = optimizerConfiguration.map.find("neededClasses");
if (classes != optimizerConfiguration.map.cend()) {
- for (const dyld3::json::Node& n : classes->second.array) {
+ for (const json::Node& n : classes->second.array) {
neededClasses[n.value] = i++;
}
}
@@ -1329,14 +1378,14 @@
if (sels != optimizerConfiguration.map.cend()) {
// TODO: The emitter for this isn't implemented yet
assert(sels->second.array.empty());
- for (const dyld3::json::Node& n : sels->second.array) {
+ for (const json::Node& n : sels->second.array) {
selectorsToInline.insert(n.value);
}
}
- const dyld3::json::Node* classHierarchiesToFlattenNode = dyld3::json::getOptionalValue(diag, optimizerConfiguration, "flatteningRoots");
+ const json::Node* classHierarchiesToFlattenNode = json::getOptionalValue(diag, optimizerConfiguration, "flatteningRoots");
if (classHierarchiesToFlattenNode != nullptr) {
- for (const dyld3::json::Node& n : classHierarchiesToFlattenNode->array) {
+ for (const json::Node& n : classHierarchiesToFlattenNode->array) {
bool metaclass = false;
const std::string *name = nameAndIsMetaclassPairFromNode(n, &metaclass);
if (metaclass) {
@@ -1379,13 +1428,14 @@
static void backtrack(std::vector<BacktrackingState>& backtrackingStack, int& numberOfDroppedClasses, std::vector<IMPCaches::ClassData*>& allClasses) {
int i = (int)backtrackingStack.size() - 1;
- assert(i>0);
+ assert(i>=0);
BacktrackingState & last = backtrackingStack.back();
if (!last.result) {
// backtracking over a skipped class
numberOfDroppedClasses--;
- }
- allClasses[i]->backtrack(*(last.result));
+ } else {
+ allClasses[i]->backtrack(*(last.result));
+ }
backtrackingStack.pop_back();
};
@@ -1635,8 +1685,8 @@
currentClassIndex = backtrackingStack.size();
dropClass(_diagnostics, currentClassIndex, numberOfDroppedClasses, backtrackingStack, randomNumberGenerator, allClasses, "it's too difficult to place");
- // FIXME: we should consider resetting backtrackingLength to the value it had when we snapshotted here (the risk makes this not worth trying at this point in the release).
-
+ // When we snapshot, we always reset the backtrackingLength, so do it here as well
+ backtrackingLength = 1;
backtrackingAttempts = 0;
continue;
} else {
@@ -1652,9 +1702,12 @@
bestSolutionSnapshotSelectors[k] = *v;
}
#endif
+
+ // This is our best solution yet so reset backtrackingLength
+ backtrackingLength = 1;
}
- _diagnostics.verbose("%lu / %lu (%s): backtracking\n", currentClassIndex, allClasses.size(), c->description().c_str());
+ _diagnostics.verbose("%lu / %lu (%s): backtracking %lu steps\n", currentClassIndex, allClasses.size(), c->description().c_str(), backtrackingLength);
assert(currentClassIndex != 0); // Backtracked all the way to the beginning, no solution
for (unsigned long j = 0 ; j < backtrackingLength ; j++) {
@@ -1765,6 +1818,26 @@
computeLowBits(holeMap);
+ // Drop all selectors and imp caches over the limit
+ droppedClasses = false;
+ for (const auto& [k,v] : selectors.map) {
+ IMPCaches::Selector* sel = v.get();
+ if ( sel->offset >= selectorSizeLimit ) {
+ _diagnostics.verbose("Dropping selector out of buffer range: '%s'\n", sel->name.data());
+
+ for ( IMPCaches::ClassData* classData : sel->classes ) {
+ if ( !classData->shouldGenerateImpCache )
+ continue;
+ classData->shouldGenerateImpCache = false;
+ droppedClasses = true;
+ _diagnostics.verbose("Dropping class %s, selectors too difficult to place\n", classData->name.data());
+ }
+ }
+ }
+
+ if ( droppedClasses )
+ removeUninterestingClasses();
+
_timeRecorder.recordTime("assign selector addresses");
_timeRecorder.popTimedSection();
}
@@ -2015,7 +2088,7 @@
namespace imp_caches
{
-Builder::Builder(const std::vector<Dylib>& dylibs, const dyld3::json::Node& objcOptimizations)
+Builder::Builder(const std::vector<Dylib>& dylibs, const json::Node& objcOptimizations)
: diags(verbose), dylibs(dylibs), objcOptimizations(objcOptimizations)
{
}
@@ -2026,9 +2099,10 @@
delete this->impCachesBuilder;
}
-void Builder::buildImpCaches()
-{
- impCachesBuilder = new IMPCaches::IMPCachesBuilder(this->diags, this->time, this->dylibs, this->objcOptimizations);
+void Builder::buildImpCaches(uint32_t selectorSizeLimit)
+{
+ impCachesBuilder = new IMPCaches::IMPCachesBuilder(this->diags, this->time, this->dylibs,
+ this->objcOptimizations, selectorSizeLimit);
// Build the class map across all dylibs (including cross-image superclass references)
impCachesBuilder->buildClassesMap(diags);