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
17package android.ext.services.storage;
18
19import android.app.usage.CacheQuotaHint;
20import android.app.usage.CacheQuotaService;
21import android.os.Environment;
22import android.os.storage.StorageManager;
23import android.os.storage.VolumeInfo;
24import android.util.ArrayMap;
25
26import java.util.ArrayList;
27import java.util.Comparator;
28import java.util.List;
29import java.util.Map;
30import java.util.stream.Collectors;
31
32/**
33 * CacheQuotaServiceImpl implements the CacheQuotaService with a strategy for populating the quota
34 * of {@link CacheQuotaHint}.
35 */
36public class CacheQuotaServiceImpl extends CacheQuotaService {
37    private static final double CACHE_RESERVE_RATIO = 0.15;
38
39    @Override
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
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
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
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