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.VolumeInfo;
24 import android.util.ArrayMap;
25 
26 import java.util.ArrayList;
27 import java.util.Comparator;
28 import java.util.List;
29 import java.util.Map;
30 import java.util.stream.Collectors;
31 
32 /**
33  * CacheQuotaServiceImpl implements the CacheQuotaService with a strategy for populating the quota
34  * of {@link CacheQuotaHint}.
35  */
36 public class CacheQuotaServiceImpl extends CacheQuotaService {
37     private static final double CACHE_RESERVE_RATIO = 0.15;
38 
39     @Override
onComputeCacheQuotaHints(List<CacheQuotaHint> requests)40     public List<CacheQuotaHint> onComputeCacheQuotaHints(List<CacheQuotaHint> requests) {
41         ArrayMap<String, List<CacheQuotaHint>> byUuid = new ArrayMap<>();
42         final int requestCount = requests.size();
43         for (int i = 0; i < requestCount; i++) {
44             CacheQuotaHint request = requests.get(i);
45             String uuid = request.getVolumeUuid();
46             List<CacheQuotaHint> listForUuid = byUuid.get(uuid);
47             if (listForUuid == null) {
48                 listForUuid = new ArrayList<>();
49                 byUuid.put(uuid, listForUuid);
50             }
51             listForUuid.add(request);
52         }
53 
54         List<CacheQuotaHint> processed = new ArrayList<>();
55         byUuid.entrySet().forEach(
56                 requestListEntry -> {
57                     // Collapse all usage stats to the same uid.
58                     Map<Integer, List<CacheQuotaHint>> byUid = requestListEntry.getValue()
59                             .stream()
60                             .collect(Collectors.groupingBy(CacheQuotaHint::getUid));
61                     byUid.values().forEach(uidGroupedList -> {
62                         int size = uidGroupedList.size();
63                         if (size < 2) {
64                             return;
65                         }
66                         CacheQuotaHint first = uidGroupedList.get(0);
67                         for (int i = 1; i < size; i++) {
68                             /* Note: We can't use the UsageStats built-in addition function because
69                                      UIDs may span multiple packages and usage stats adding has
70                                      matching package names as a precondition. */
71                             first.getUsageStats().mTotalTimeInForeground +=
72                                     uidGroupedList.get(i).getUsageStats().mTotalTimeInForeground;
73                         }
74                     });
75 
76                     // Because the foreground stats have been added to the first element, we need
77                     // a list of only the first values (which contain the merged foreground time).
78                     List<CacheQuotaHint> flattenedRequests =
79                             byUid.values()
80                                  .stream()
81                                  .map(entryList -> entryList.get(0))
82                                  .filter(entry -> entry.getUsageStats().mTotalTimeInForeground != 0)
83                                  .sorted(sCacheQuotaRequestComparator)
84                                  .collect(Collectors.toList());
85 
86                     // Because the elements are sorted, we can use the index to also be the sorted
87                     // index for cache quota calculation.
88                     double sum = getSumOfFairShares(flattenedRequests.size());
89                     String uuid = requestListEntry.getKey();
90                     long reservedSize = getReservedCacheSize(uuid);
91                     for (int count = 0; count < flattenedRequests.size(); count++) {
92                         double share = getFairShareForPosition(count) / sum;
93                         CacheQuotaHint entry = flattenedRequests.get(count);
94                         CacheQuotaHint.Builder builder = new CacheQuotaHint.Builder(entry);
95                         builder.setQuota(Math.round(share * reservedSize));
96                         processed.add(builder.build());
97                     }
98                 }
99         );
100 
101         return processed.stream()
102                 .filter(request -> request.getQuota() > 0).collect(Collectors.toList());
103     }
104 
getFairShareForPosition(int position)105     private double getFairShareForPosition(int position) {
106         double value = 1.0 / Math.log(position + 3) - 0.285;
107         return (value > 0.01) ? value : 0.01;
108     }
109 
getSumOfFairShares(int size)110     private double getSumOfFairShares(int size) {
111         double sum = 0;
112         for (int i = 0; i < size; i++) {
113             sum += getFairShareForPosition(i);
114         }
115         return sum;
116     }
117 
getReservedCacheSize(String uuid)118     private long getReservedCacheSize(String uuid) {
119         // TODO: Revisit the cache size after running more storage tests.
120         // TODO: Figure out how to ensure ExtServices has the permissions to call
121         //       StorageStatsManager, because this is ignoring the cache...
122         StorageManager storageManager = getSystemService(StorageManager.class);
123         long freeBytes = 0;
124         if (uuid == StorageManager.UUID_PRIVATE_INTERNAL) { // regular equals because of null
125             freeBytes = Environment.getDataDirectory().getUsableSpace();
126         } else {
127             final VolumeInfo vol = storageManager.findVolumeByUuid(uuid);
128             freeBytes = vol.getPath().getUsableSpace();
129         }
130         return Math.round(freeBytes * CACHE_RESERVE_RATIO);
131     }
132 
133     // Compares based upon foreground time.
134     private static Comparator<CacheQuotaHint> sCacheQuotaRequestComparator =
135             new Comparator<CacheQuotaHint>() {
136         @Override
137         public int compare(CacheQuotaHint o, CacheQuotaHint t1) {
138             long x = t1.getUsageStats().getTotalTimeInForeground();
139             long y = o.getUsageStats().getTotalTimeInForeground();
140             return (x < y) ? -1 : ((x == y) ? 0 : 1);
141         }
142     };
143 }
144