ClientManager.h revision cc776718c0be7c31fe5ab4fc1446d377be60369f
1/* 2 * Copyright (C) 2015 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#ifndef ANDROID_SERVICE_UTILS_EVICTION_POLICY_MANAGER_H 18#define ANDROID_SERVICE_UTILS_EVICTION_POLICY_MANAGER_H 19 20#include <utils/Mutex.h> 21 22#include <algorithm> 23#include <utility> 24#include <vector> 25#include <set> 26#include <map> 27#include <memory> 28 29namespace android { 30namespace resource_policy { 31 32// -------------------------------------------------------------------------------- 33 34/** 35 * The ClientDescriptor class is a container for a given key/value pair identifying a shared 36 * resource, and the corresponding cost, priority, owner ID, and conflicting keys list used 37 * in determining eviction behavior. 38 * 39 * Aside from the priority, these values are immutable once the ClientDescriptor has been 40 * constructed. 41 */ 42template<class KEY, class VALUE> 43class ClientDescriptor final { 44public: 45 ClientDescriptor(const KEY& key, const VALUE& value, int32_t cost, 46 const std::set<KEY>& conflictingKeys, int32_t priority, int32_t ownerId); 47 ClientDescriptor(KEY&& key, VALUE&& value, int32_t cost, std::set<KEY>&& conflictingKeys, 48 int32_t priority, int32_t ownerId); 49 50 ~ClientDescriptor(); 51 52 /** 53 * Return the key for this descriptor. 54 */ 55 const KEY& getKey() const; 56 57 /** 58 * Return the value for this descriptor. 59 */ 60 const VALUE& getValue() const; 61 62 /** 63 * Return the cost for this descriptor. 64 */ 65 int32_t getCost() const; 66 67 /** 68 * Return the priority for this descriptor. 69 */ 70 int32_t getPriority() const; 71 72 /** 73 * Return the owner ID for this descriptor. 74 */ 75 int32_t getOwnerId() const; 76 77 /** 78 * Return true if the given key is in this descriptor's conflicting keys list. 79 */ 80 bool isConflicting(const KEY& key) const; 81 82 /** 83 * Return the set of all conflicting keys for this descriptor. 84 */ 85 std::set<KEY> getConflicting() const; 86 87 /** 88 * Set the proirity for this descriptor. 89 */ 90 void setPriority(int32_t priority); 91 92 // This class is ordered by key 93 template<class K, class V> 94 friend bool operator < (const ClientDescriptor<K, V>& a, const ClientDescriptor<K, V>& b); 95 96private: 97 KEY mKey; 98 VALUE mValue; 99 int32_t mCost; 100 std::set<KEY> mConflicting; 101 int32_t mPriority; 102 int32_t mOwnerId; 103}; // class ClientDescriptor 104 105template<class K, class V> 106bool operator < (const ClientDescriptor<K, V>& a, const ClientDescriptor<K, V>& b) { 107 return a.mKey < b.mKey; 108} 109 110template<class KEY, class VALUE> 111ClientDescriptor<KEY, VALUE>::ClientDescriptor(const KEY& key, const VALUE& value, int32_t cost, 112 const std::set<KEY>& conflictingKeys, int32_t priority, int32_t ownerId) : mKey{key}, 113 mValue{value}, mCost{cost}, mConflicting{conflictingKeys}, mPriority{priority}, 114 mOwnerId{ownerId} {} 115 116template<class KEY, class VALUE> 117ClientDescriptor<KEY, VALUE>::ClientDescriptor(KEY&& key, VALUE&& value, int32_t cost, 118 std::set<KEY>&& conflictingKeys, int32_t priority, int32_t ownerId) : 119 mKey{std::forward<KEY>(key)}, mValue{std::forward<VALUE>(value)}, mCost{cost}, 120 mConflicting{std::forward<std::set<KEY>>(conflictingKeys)}, mPriority{priority}, 121 mOwnerId{ownerId} {} 122 123template<class KEY, class VALUE> 124ClientDescriptor<KEY, VALUE>::~ClientDescriptor() {} 125 126template<class KEY, class VALUE> 127const KEY& ClientDescriptor<KEY, VALUE>::getKey() const { 128 return mKey; 129} 130 131template<class KEY, class VALUE> 132const VALUE& ClientDescriptor<KEY, VALUE>::getValue() const { 133 return mValue; 134} 135 136template<class KEY, class VALUE> 137int32_t ClientDescriptor<KEY, VALUE>::getCost() const { 138 return mCost; 139} 140 141template<class KEY, class VALUE> 142int32_t ClientDescriptor<KEY, VALUE>::getPriority() const { 143 return mPriority; 144} 145 146template<class KEY, class VALUE> 147int32_t ClientDescriptor<KEY, VALUE>::getOwnerId() const { 148 return mOwnerId; 149} 150 151template<class KEY, class VALUE> 152bool ClientDescriptor<KEY, VALUE>::isConflicting(const KEY& key) const { 153 if (key == mKey) return true; 154 for (const auto& x : mConflicting) { 155 if (key == x) return true; 156 } 157 return false; 158} 159 160template<class KEY, class VALUE> 161std::set<KEY> ClientDescriptor<KEY, VALUE>::getConflicting() const { 162 return mConflicting; 163} 164 165template<class KEY, class VALUE> 166void ClientDescriptor<KEY, VALUE>::setPriority(int32_t priority) { 167 mPriority = priority; 168} 169 170// -------------------------------------------------------------------------------- 171 172/** 173 * The ClientManager class wraps an LRU-ordered list of active clients and implements eviction 174 * behavior for handling shared resource access. 175 * 176 * When adding a new descriptor, eviction behavior is as follows: 177 * - Keys are unique, adding a descriptor with the same key as an existing descriptor will 178 * result in the lower-priority of the two being removed. Priority ties result in the 179 * LRU descriptor being evicted (this means the incoming descriptor be added in this case). 180 * - Any descriptors with keys that are in the incoming descriptor's 'conflicting keys' list 181 * will be removed if they have an equal or lower priority than the incoming descriptor; 182 * if any have a higher priority, the incoming descriptor is removed instead. 183 * - If the sum of all descriptors' costs, including the incoming descriptor's, is more than 184 * the max cost allowed for this ClientManager, descriptors with non-zero cost, equal or lower 185 * priority, and a different owner will be evicted in LRU order until either the cost is less 186 * than the max cost, or all descriptors meeting this criteria have been evicted and the 187 * incoming descriptor has the highest priority. Otherwise, the incoming descriptor is 188 * removed instead. 189 */ 190template<class KEY, class VALUE> 191class ClientManager { 192public: 193 // The default maximum "cost" allowed before evicting 194 static constexpr int32_t DEFAULT_MAX_COST = 100; 195 196 ClientManager(); 197 ClientManager(int32_t totalCost); 198 199 /** 200 * Add a given ClientDescriptor to the managed list. ClientDescriptors for clients that 201 * are evicted by this action are returned in a vector. 202 * 203 * This may return the ClientDescriptor passed in if it would be evicted. 204 */ 205 std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> addAndEvict( 206 const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& client); 207 208 /** 209 * Given a map containing owner (pid) -> priority mappings, update the priority of each 210 * ClientDescriptor with an owner in this mapping. 211 */ 212 void updatePriorities(const std::map<int32_t,int32_t>& ownerPriorityList); 213 214 /** 215 * Remove all ClientDescriptors. 216 */ 217 void removeAll(); 218 219 /** 220 * Remove and return the ClientDescriptor with a given key. 221 */ 222 std::shared_ptr<ClientDescriptor<KEY, VALUE>> remove(const KEY& key); 223 224 /** 225 * Remove the given ClientDescriptor. 226 */ 227 void remove(const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& value); 228 229 /** 230 * Return a vector of the ClientDescriptors that would be evicted by adding the given 231 * ClientDescriptor. 232 * 233 * This may return the ClientDescriptor passed in if it would be evicted. 234 */ 235 std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> wouldEvict( 236 const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& client) const; 237 238 /** 239 * Return a vector of active ClientDescriptors that prevent this client from being added. 240 */ 241 std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> getIncompatibleClients( 242 const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& client) const; 243 244 /** 245 * Return a vector containing all currently active ClientDescriptors. 246 */ 247 std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> getAll() const; 248 249 /** 250 * Return a vector containing all keys of currently active ClientDescriptors. 251 */ 252 std::vector<KEY> getAllKeys() const; 253 254 /** 255 * Return a vector of the owner tags of all currently active ClientDescriptors (duplicates 256 * will be removed). 257 */ 258 std::vector<int32_t> getAllOwners() const; 259 260 /** 261 * Return the ClientDescriptor corresponding to the given key, or an empty shared pointer 262 * if none exists. 263 */ 264 std::shared_ptr<ClientDescriptor<KEY, VALUE>> get(const KEY& key) const; 265 266protected: 267 ~ClientManager(); 268 269private: 270 271 /** 272 * Return a vector of the ClientDescriptors that would be evicted by adding the given 273 * ClientDescriptor. If returnIncompatibleClients is set to true, instead, return the 274 * vector of ClientDescriptors that are higher priority than the incoming client and 275 * either conflict with this client, or contribute to the resource cost if that would 276 * prevent the incoming client from being added. 277 * 278 * This may return the ClientDescriptor passed in. 279 */ 280 std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> wouldEvictLocked( 281 const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& client, 282 bool returnIncompatibleClients = false) const; 283 284 int64_t getCurrentCostLocked() const; 285 286 mutable Mutex mLock; 287 int32_t mMaxCost; 288 // LRU ordered, most recent at end 289 std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> mClients; 290}; // class ClientManager 291 292template<class KEY, class VALUE> 293ClientManager<KEY, VALUE>::ClientManager() : 294 ClientManager(DEFAULT_MAX_COST) {} 295 296template<class KEY, class VALUE> 297ClientManager<KEY, VALUE>::ClientManager(int32_t totalCost) : mMaxCost(totalCost) {} 298 299template<class KEY, class VALUE> 300ClientManager<KEY, VALUE>::~ClientManager() {} 301 302template<class KEY, class VALUE> 303std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> ClientManager<KEY, VALUE>::wouldEvict( 304 const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& client) const { 305 Mutex::Autolock lock(mLock); 306 return wouldEvictLocked(client); 307} 308 309template<class KEY, class VALUE> 310std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> 311ClientManager<KEY, VALUE>::getIncompatibleClients( 312 const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& client) const { 313 Mutex::Autolock lock(mLock); 314 return wouldEvictLocked(client, /*returnIncompatibleClients*/true); 315} 316 317template<class KEY, class VALUE> 318std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> 319ClientManager<KEY, VALUE>::wouldEvictLocked( 320 const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& client, 321 bool returnIncompatibleClients) const { 322 323 std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> evictList; 324 325 // Disallow null clients, return input 326 if (client == nullptr) { 327 evictList.push_back(client); 328 return evictList; 329 } 330 331 const KEY& key = client->getKey(); 332 int32_t cost = client->getCost(); 333 int32_t priority = client->getPriority(); 334 int32_t owner = client->getOwnerId(); 335 336 int64_t totalCost = getCurrentCostLocked() + cost; 337 338 // Determine the MRU of the owners tied for having the highest priority 339 int32_t highestPriorityOwner = owner; 340 int32_t highestPriority = priority; 341 for (const auto& i : mClients) { 342 int32_t curPriority = i->getPriority(); 343 if (curPriority >= highestPriority) { 344 highestPriority = curPriority; 345 highestPriorityOwner = i->getOwnerId(); 346 } 347 } 348 349 if (highestPriority == priority) { 350 // Switch back owner if the incoming client has the highest priority, as it is MRU 351 highestPriorityOwner = owner; 352 } 353 354 // Build eviction list of clients to remove 355 for (const auto& i : mClients) { 356 const KEY& curKey = i->getKey(); 357 int32_t curCost = i->getCost(); 358 int32_t curPriority = i->getPriority(); 359 int32_t curOwner = i->getOwnerId(); 360 361 bool conflicting = (curKey == key || i->isConflicting(key) || 362 client->isConflicting(curKey)); 363 364 if (!returnIncompatibleClients) { 365 // Find evicted clients 366 367 if (conflicting && curPriority > priority) { 368 // Pre-existing conflicting client with higher priority exists 369 evictList.clear(); 370 evictList.push_back(client); 371 return evictList; 372 } else if (conflicting || ((totalCost > mMaxCost && curCost > 0) && 373 (curPriority <= priority) && 374 !(highestPriorityOwner == owner && owner == curOwner))) { 375 // Add a pre-existing client to the eviction list if: 376 // - We are adding a client with higher priority that conflicts with this one. 377 // - The total cost including the incoming client's is more than the allowable 378 // maximum, and the client has a non-zero cost, lower priority, and a different 379 // owner than the incoming client when the incoming client has the 380 // highest priority. 381 evictList.push_back(i); 382 totalCost -= curCost; 383 } 384 } else { 385 // Find clients preventing the incoming client from being added 386 387 if (curPriority > priority && (conflicting || (totalCost > mMaxCost && curCost > 0))) { 388 // Pre-existing conflicting client with higher priority exists 389 evictList.push_back(i); 390 } 391 } 392 } 393 394 // Immediately return the incompatible clients if we are calculating these instead 395 if (returnIncompatibleClients) { 396 return evictList; 397 } 398 399 // If the total cost is too high, return the input unless the input has the highest priority 400 if (totalCost > mMaxCost && highestPriorityOwner != owner) { 401 evictList.clear(); 402 evictList.push_back(client); 403 return evictList; 404 } 405 406 return evictList; 407 408} 409 410template<class KEY, class VALUE> 411std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> ClientManager<KEY, VALUE>::addAndEvict( 412 const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& client) { 413 Mutex::Autolock lock(mLock); 414 auto evicted = wouldEvictLocked(client); 415 auto it = evicted.begin(); 416 if (it != evicted.end() && *it == client) { 417 return evicted; 418 } 419 420 auto iter = evicted.cbegin(); 421 422 // Remove evicted clients from list 423 mClients.erase(std::remove_if(mClients.begin(), mClients.end(), 424 [&iter] (std::shared_ptr<ClientDescriptor<KEY, VALUE>>& curClientPtr) { 425 if (curClientPtr->getKey() == (*iter)->getKey()) { 426 iter++; 427 return true; 428 } 429 return false; 430 }), mClients.end()); 431 432 mClients.push_back(client); 433 434 return evicted; 435} 436 437template<class KEY, class VALUE> 438std::vector<std::shared_ptr<ClientDescriptor<KEY, VALUE>>> 439ClientManager<KEY, VALUE>::getAll() const { 440 Mutex::Autolock lock(mLock); 441 return mClients; 442} 443 444template<class KEY, class VALUE> 445std::vector<KEY> ClientManager<KEY, VALUE>::getAllKeys() const { 446 Mutex::Autolock lock(mLock); 447 std::vector<KEY> keys(mClients.size()); 448 for (const auto& i : mClients) { 449 keys.push_back(i->getKey()); 450 } 451 return keys; 452} 453 454template<class KEY, class VALUE> 455std::vector<int32_t> ClientManager<KEY, VALUE>::getAllOwners() const { 456 Mutex::Autolock lock(mLock); 457 std::set<int32_t> owners; 458 for (const auto& i : mClients) { 459 owners.emplace(i->getOwnerId()); 460 } 461 return std::vector<int32_t>(owners.begin(), owners.end()); 462} 463 464template<class KEY, class VALUE> 465void ClientManager<KEY, VALUE>::updatePriorities( 466 const std::map<int32_t,int32_t>& ownerPriorityList) { 467 Mutex::Autolock lock(mLock); 468 for (auto& i : mClients) { 469 auto j = ownerPriorityList.find(i->getOwnerId()); 470 if (j != ownerPriorityList.end()) { 471 i->setPriority(j->second); 472 } 473 } 474} 475 476template<class KEY, class VALUE> 477std::shared_ptr<ClientDescriptor<KEY, VALUE>> ClientManager<KEY, VALUE>::get( 478 const KEY& key) const { 479 Mutex::Autolock lock(mLock); 480 for (const auto& i : mClients) { 481 if (i->getKey() == key) return i; 482 } 483 return std::shared_ptr<ClientDescriptor<KEY, VALUE>>(nullptr); 484} 485 486template<class KEY, class VALUE> 487void ClientManager<KEY, VALUE>::removeAll() { 488 Mutex::Autolock lock(mLock); 489 mClients.clear(); 490} 491 492template<class KEY, class VALUE> 493std::shared_ptr<ClientDescriptor<KEY, VALUE>> ClientManager<KEY, VALUE>::remove(const KEY& key) { 494 Mutex::Autolock lock(mLock); 495 496 std::shared_ptr<ClientDescriptor<KEY, VALUE>> ret; 497 498 // Remove evicted clients from list 499 mClients.erase(std::remove_if(mClients.begin(), mClients.end(), 500 [&key, &ret] (std::shared_ptr<ClientDescriptor<KEY, VALUE>>& curClientPtr) { 501 if (curClientPtr->getKey() == key) { 502 ret = curClientPtr; 503 return true; 504 } 505 return false; 506 }), mClients.end()); 507 508 return ret; 509} 510 511template<class KEY, class VALUE> 512void ClientManager<KEY, VALUE>::remove( 513 const std::shared_ptr<ClientDescriptor<KEY, VALUE>>& value) { 514 Mutex::Autolock lock(mLock); 515 // Remove evicted clients from list 516 mClients.erase(std::remove_if(mClients.begin(), mClients.end(), 517 [&value] (std::shared_ptr<ClientDescriptor<KEY, VALUE>>& curClientPtr) { 518 if (curClientPtr == value) { 519 return true; 520 } 521 return false; 522 }), mClients.end()); 523} 524 525template<class KEY, class VALUE> 526int64_t ClientManager<KEY, VALUE>::getCurrentCostLocked() const { 527 int64_t totalCost = 0; 528 for (const auto& x : mClients) { 529 totalCost += x->getCost(); 530 } 531 return totalCost; 532} 533 534// -------------------------------------------------------------------------------- 535 536}; // namespace resource_policy 537}; // namespace android 538 539#endif // ANDROID_SERVICE_UTILS_EVICTION_POLICY_MANAGER_H 540