1 /*
2  * Copyright (C) 2017 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 package android.ext.services.storage;
18 
19 import android.app.usage.CacheQuotaHint;
20 import android.app.usage.CacheQuotaService;
21 import android.os.Environment;
22 import android.os.storage.StorageManager;
23 import android.os.storage.StorageVolume;
24 import android.text.TextUtils;
25 import android.util.ArrayMap;
26 
27 import androidx.core.util.Preconditions;
28 
29 import com.android.modules.utils.build.SdkLevel;
30 
31 import java.io.File;
32 import java.util.ArrayList;
33 import java.util.Comparator;
34 import java.util.List;
35 import java.util.Map;
36 import java.util.stream.Collectors;
37 
38 /**
39  * CacheQuotaServiceImpl implements the CacheQuotaService with a strategy for populating the quota
40  * of {@link CacheQuotaHint}.
41  */
42 public class CacheQuotaServiceImpl extends CacheQuotaService {
43 
44     @Override
onComputeCacheQuotaHints(List<CacheQuotaHint> requests)45     public List<CacheQuotaHint> onComputeCacheQuotaHints(List<CacheQuotaHint> requests) {
46         ArrayMap<String, List<CacheQuotaHintExtend>> byUuid = new ArrayMap<>();
47         final int requestCount = requests.size();
48         for (int i = 0; i < requestCount; i++) {
49             CacheQuotaHint request = requests.get(i);
50             String uuid = request.getVolumeUuid();
51             List<CacheQuotaHintExtend> listForUuid = byUuid.get(uuid);
52             if (listForUuid == null) {
53                 listForUuid = new ArrayList<>();
54                 byUuid.put(uuid, listForUuid);
55             }
56             listForUuid.add(convertToCacheQuotaHintExtend(request));
57         }
58 
59         List<CacheQuotaHint> processed = new ArrayList<>();
60         byUuid.forEach((uuid, uuidGroupedList) -> {
61             // Collapse all usage stats to the same uid.
62             Map<Integer, List<CacheQuotaHintExtend>> byUid = uuidGroupedList
63                     .stream()
64                     .collect(Collectors.groupingBy(CacheQuotaHintExtend::getUid));
65             byUid.values().forEach(uidGroupedList -> {
66                 int size = uidGroupedList.size();
67                 if (size < 2) {
68                     return;
69                 }
70                 CacheQuotaHintExtend first = uidGroupedList.get(0);
71                 for (int i = 1; i < size; i++) {
72                     /* Note: We can't use the UsageStats built-in addition function because
73                              UIDs may span multiple packages and usage stats adding has
74                              matching package names as a precondition. */
75                     first.mTotalTimeInForeground +=
76                             uidGroupedList.get(i).mTotalTimeInForeground;
77                 }
78             });
79 
80             // Because the foreground stats have been added to the first element, we need
81             // a list of only the first values (which contain the merged foreground time).
82             List<CacheQuotaHintExtend> flattenedRequests =
83                     byUid.values()
84                             .stream()
85                             .map(entryList -> entryList.get(0))
86                             .filter(entry -> entry.mTotalTimeInForeground != 0)
87                             .sorted(sCacheQuotaRequestComparator)
88                             .collect(Collectors.toList());
89 
90             // Because the elements are sorted, we can use the index to also be the sorted
91             // index for cache quota calculation.
92             double sum = getSumOfFairShares(flattenedRequests.size());
93             long reservedSize = getReservedCacheSize(uuid);
94             final int flattenedRequestsSize = flattenedRequests.size();
95             for (int count = 0; count < flattenedRequestsSize; count++) {
96                 double share = getFairShareForPosition(count) / sum;
97                 CacheQuotaHint entry = flattenedRequests.get(count).mCacheQuotaHint;
98                 CacheQuotaHint.Builder builder = new CacheQuotaHint.Builder(entry);
99                 builder.setQuota(Math.round(share * reservedSize));
100                 processed.add(builder.build());
101             }
102 
103             // Calculate the median of quotas of uids with >0 foreground time
104             int midPoint = flattenedRequests.size() / 2;
105             double medianValue, share;
106             long medianQuota;
107             if (flattenedRequests.size() % 2 == 0) {
108                 medianValue = (getFairShareForPosition(midPoint - 1)
109                         + getFairShareForPosition(midPoint)) / 2;
110             } else {
111                 medianValue = getFairShareForPosition(midPoint);
112             }
113             share = medianValue / sum;
114             medianQuota = Math.round(share * reservedSize);
115             // Allot median quota to uids with foreground time =0
116             List<CacheQuotaHintExtend> flattenedRequestsForegroundZero =
117                     byUid.values()
118                             .stream()
119                             .map(entryList -> entryList.get(0))
120                             .filter(entry -> entry.mTotalTimeInForeground == 0)
121                             .sorted(sCacheQuotaRequestComparator)
122                             .collect(Collectors.toList());
123             final int flattenedRequestsForegroundZeroSize = flattenedRequestsForegroundZero.size();
124             for (int count = 0; count < flattenedRequestsForegroundZeroSize; count++) {
125                 CacheQuotaHint entry = flattenedRequestsForegroundZero.get(count)
126                         .mCacheQuotaHint;
127                 CacheQuotaHint.Builder builder = new CacheQuotaHint.Builder(entry);
128                 builder.setQuota(medianQuota);
129                 processed.add(builder.build());
130             }
131         });
132 
133         return processed.stream()
134                 .filter(request -> request.getQuota() > 0).collect(Collectors.toList());
135     }
136 
getFairShareForPosition(int position)137     private double getFairShareForPosition(int position) {
138         double value = 1.0 / Math.log(position + 3) - 0.285;
139         return (value > 0.01) ? value : 0.01;
140     }
141 
getSumOfFairShares(int size)142     private double getSumOfFairShares(int size) {
143         double sum = 0;
144         for (int i = 0; i < size; i++) {
145             sum += getFairShareForPosition(i);
146         }
147         return sum;
148     }
149 
getReservedCacheSize(String uuid)150     private long getReservedCacheSize(String uuid) {
151         // TODO: Revisit the cache size after running more storage tests.
152         // TODO: Figure out how to ensure ExtServices has the permissions to call
153         //       StorageStatsManager, because this is ignoring the cache...
154         final long cacheReservePercent = 15;
155         final StorageManager storageManager = getSystemService(StorageManager.class);
156         if (TextUtils.isEmpty(uuid)) { // regular equals because of null
157             if (SdkLevel.isAtLeastT()) {
158                 return storageManager.computeStorageCacheBytes(Environment.getDataDirectory());
159             } else {
160                 return Environment.getDataDirectory().getUsableSpace()
161                         * cacheReservePercent / 100;
162             }
163         } else {
164             final List<StorageVolume> storageVolumes = storageManager.getStorageVolumes();
165             final int volumeCount = storageVolumes.size();
166             for (int i = 0; i < volumeCount; i++) {
167                 final StorageVolume volume = storageVolumes.get(i);
168                 if (TextUtils.equals(volume.getUuid(), uuid)) {
169                     final File directory = volume.getDirectory();
170                     if (SdkLevel.isAtLeastT()) {
171                         return storageManager.computeStorageCacheBytes(directory);
172                     } else {
173                         return ((directory != null) ? directory.getUsableSpace() : 0)
174                                 * cacheReservePercent / 100;
175                     }
176                 }
177             }
178         }
179         return 0;
180     }
181 
182     // Compares based upon foreground time.
183     private static Comparator<CacheQuotaHintExtend> sCacheQuotaRequestComparator =
184             new Comparator<CacheQuotaHintExtend>() {
185         @Override
186         public int compare(CacheQuotaHintExtend o, CacheQuotaHintExtend t1) {
187             return (t1.mTotalTimeInForeground < o.mTotalTimeInForeground) ?
188                     -1 : ((t1.mTotalTimeInForeground == o.mTotalTimeInForeground) ? 0 : 1);
189         }
190     };
191 
convertToCacheQuotaHintExtend(CacheQuotaHint cacheQuotaHint)192     private CacheQuotaHintExtend convertToCacheQuotaHintExtend(CacheQuotaHint cacheQuotaHint) {
193         Preconditions.checkNotNull(cacheQuotaHint);
194         return new CacheQuotaHintExtend(cacheQuotaHint);
195     }
196 
197     private final class CacheQuotaHintExtend {
198         public final CacheQuotaHint mCacheQuotaHint;
199         public long mTotalTimeInForeground;
200 
CacheQuotaHintExtend(CacheQuotaHint cacheQuotaHint)201         public CacheQuotaHintExtend (CacheQuotaHint cacheQuotaHint) {
202             mCacheQuotaHint = cacheQuotaHint;
203             mTotalTimeInForeground = (cacheQuotaHint.getUsageStats() != null) ?
204                     cacheQuotaHint.getUsageStats().getTotalTimeInForeground() : 0;
205         }
206 
getUid()207         public int getUid() {
208             return mCacheQuotaHint.getUid();
209         }
210     }
211 }
212