1 /*
2  * Copyright (C) 2023 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 com.android.server.wifi;
18 
19 import android.net.wifi.QosPolicyParams;
20 import android.net.wifi.WifiManager;
21 
22 import com.android.modules.utils.build.SdkLevel;
23 
24 import java.io.PrintWriter;
25 import java.util.ArrayDeque;
26 import java.util.ArrayList;
27 import java.util.HashMap;
28 import java.util.List;
29 import java.util.Map;
30 import java.util.Queue;
31 import java.util.stream.Stream;
32 
33 /**
34  * Table containing application-added QoS policies that are being tracked by the framework.
35  */
36 public class ApplicationQosPolicyTrackingTable {
37     private Queue<Integer> mAvailableVirtualPolicyIds = new ArrayDeque<>();
38 
39     // Mapping between a policy hash and a policy object.
40     // See combinePolicyIdAndUid() for more information about the policy hash format.
41     private Map<Long, QosPolicyParams> mPolicyHashToPolicyMap = new HashMap<>();
42     private Map<Integer, List<Long>> mUidToPolicyHashesMap = new HashMap<>();
43 
ApplicationQosPolicyTrackingTable(int minVirtualPolicyId, int maxVirtualPolicyId)44     public ApplicationQosPolicyTrackingTable(int minVirtualPolicyId, int maxVirtualPolicyId) {
45         for (int i = minVirtualPolicyId; i <= maxVirtualPolicyId; i++) {
46             mAvailableVirtualPolicyIds.add(i);
47         }
48     }
49 
generateStatusList( int size, @WifiManager.QosRequestStatus int statusCode)50     private List<Integer> generateStatusList(
51             int size, @WifiManager.QosRequestStatus int statusCode) {
52         List<Integer> statusList = new ArrayList<>();
53         for (int i = 0; i < size; i++) {
54             statusList.add(statusCode);
55         }
56         return statusList;
57     }
58 
59     /**
60      * Combine the provided policyId and UID into a long with the format:
61      *
62      * | Bits 63-32 | Bits 31-0 |
63      * |------------|-----------|
64      * |  policyId  |    uid    |
65      *
66      * Long can be used as a unique hash identifying each policy in the table.
67      */
combinePolicyIdAndUid(int policyId, int uid)68     private static long combinePolicyIdAndUid(int policyId, int uid) {
69         long shiftedPolicyId = Integer.toUnsignedLong(policyId) << 32;
70         return shiftedPolicyId | Integer.toUnsignedLong(uid);
71     }
72 
getPolicyIdFromCombinedLong(long combined)73     private static int getPolicyIdFromCombinedLong(long combined) {
74         return (int) (combined >> 32);
75     }
76 
getUidFromCombinedLong(long combined)77     private static int getUidFromCombinedLong(long combined) {
78         return (int) (combined & 0xFFFFFFFF);
79     }
80 
81     /**
82      * Add a list of QoS policies to the tracking table.
83      *
84      * Each accepted policy will be assigned a virtual policy ID using
85      * {@link QosPolicyParams#setTranslatedPolicyId(int)}.
86      *
87      * @param policies List of policies to add.
88      * @param uid UID of the requesting application.
89      * @return List of status codes from {@link WifiManager.QosRequestStatus}. Status list will be
90      *         the same length as the input list, and each status code will correspond to the
91      *         policy at that index in the input list.
92      */
addPolicies(List<QosPolicyParams> policies, int uid)93     public List<Integer> addPolicies(List<QosPolicyParams> policies, int uid) {
94         if (mAvailableVirtualPolicyIds.size() < policies.size()) {
95             // Not enough space in the table.
96             return generateStatusList(
97                     policies.size(), WifiManager.QOS_REQUEST_STATUS_INSUFFICIENT_RESOURCES);
98         }
99         List<Integer> statusList = generateStatusList(
100                 policies.size(), WifiManager.QOS_REQUEST_STATUS_TRACKING);
101 
102         for (int i = 0; i < policies.size(); i++) {
103             QosPolicyParams policy = policies.get(i);
104             long policyHash = combinePolicyIdAndUid(policy.getPolicyId(), uid);
105             if (mPolicyHashToPolicyMap.containsKey(policyHash)) {
106                 // Policy is already in the table.
107                 statusList.set(i, WifiManager.QOS_REQUEST_STATUS_ALREADY_ACTIVE);
108                 continue;
109             }
110 
111             int virtualPolicyId = mAvailableVirtualPolicyIds.remove();
112             policy.setTranslatedPolicyId(virtualPolicyId);
113             mPolicyHashToPolicyMap.put(policyHash, policy);
114             if (!mUidToPolicyHashesMap.containsKey(uid)) {
115                 mUidToPolicyHashesMap.put(uid, new ArrayList<>());
116             }
117             mUidToPolicyHashesMap.get(uid).add(policyHash);
118         }
119         return statusList;
120     }
121 
122     /**
123      * Remove a list of policies from the tracking table.
124      *
125      * Method should be considered best-effort. Any policies in the batch
126      * that are not found will be silently ignored.
127      *
128      * @param policyIds List of policy IDs which should be removed.
129      * @param uid UID of the requesting application.
130      */
removePolicies(List<Integer> policyIds, int uid)131     public void removePolicies(List<Integer> policyIds, int uid) {
132         for (int policyId : policyIds) {
133             long policyHash = combinePolicyIdAndUid(policyId, uid);
134             QosPolicyParams policy = mPolicyHashToPolicyMap.get(policyHash);
135             if (policy == null) {
136                 continue;
137             }
138             int virtualPolicyId = policy.getTranslatedPolicyId();
139             mAvailableVirtualPolicyIds.add(virtualPolicyId);
140             mPolicyHashToPolicyMap.remove(policyHash);
141             mUidToPolicyHashesMap.get(uid).remove(Long.valueOf(policyHash));
142             if (mUidToPolicyHashesMap.get(uid).isEmpty()) {
143                 mUidToPolicyHashesMap.remove(uid);
144             }
145         }
146     }
147 
148     /**
149      * Given a list of policies, filter out any polices that are not tracked by the table.
150      *
151      * @param policyList List of policies to filter.
152      * @param uid UID of the requesting application.
153      * @return Filtered list of policies, containing only the policies that are in the table.
154      */
filterUntrackedPolicies( List<QosPolicyParams> policyList, int uid)155     public List<QosPolicyParams> filterUntrackedPolicies(
156             List<QosPolicyParams> policyList, int uid) {
157         List<QosPolicyParams> trackedPolicies = new ArrayList<>();
158         for (QosPolicyParams policy : policyList) {
159             long policyHash = combinePolicyIdAndUid(policy.getPolicyId(), uid);
160             if (mPolicyHashToPolicyMap.containsKey(policyHash)) {
161                 trackedPolicies.add(policy);
162             }
163         }
164         return trackedPolicies;
165     }
166 
167     /**
168      * Translate a list of physical policy IDs to virtual.
169      *
170      * Method should be considered best-effort. Any policies in the batch
171      * that are not found will be silently excluded from the returned list.
172      *
173      * @param policyIds List of policy IDs to translate.
174      * @param uid UID of the requesting application.
175      * @return List of virtual policy IDs.
176      */
translatePolicyIds(List<Integer> policyIds, int uid)177     public List<Integer> translatePolicyIds(List<Integer> policyIds, int uid) {
178         List<Integer> virtualPolicyIds = new ArrayList<>();
179         for (int policyId : policyIds) {
180             long policyHash = combinePolicyIdAndUid(policyId, uid);
181             QosPolicyParams policy = mPolicyHashToPolicyMap.get(policyHash);
182             if (policy == null) {
183                 continue;
184             }
185             virtualPolicyIds.add(policy.getTranslatedPolicyId());
186         }
187         return virtualPolicyIds;
188     }
189 
190     /**
191      * Retrieve the IDs for all policies owned by this requester.
192      *
193      * @param uid UID of the requesting application.
194      * @return List of policy IDs.
195      */
getAllPolicyIdsOwnedByUid(int uid)196     public List<Integer> getAllPolicyIdsOwnedByUid(int uid) {
197         List<Integer> policyIds = new ArrayList<>();
198         List<Long> policyHashes = mUidToPolicyHashesMap.get(uid);
199         if (policyHashes == null) return policyIds;
200         for (long policyHash : policyHashes) {
201             int policyId = getPolicyIdFromCombinedLong(policyHash);
202             policyIds.add(policyId);
203         }
204         return policyIds;
205     }
206 
207     /**
208      * Check whether this requester owns any policies in the table.
209      *
210      * @param uid UID of the requesting application.
211      * @return true if the requester owns any policies in the table, false otherwise.
212      */
tableContainsUid(int uid)213     public boolean tableContainsUid(int uid) {
214         return mUidToPolicyHashesMap.containsKey(uid);
215     }
216 
217     /**
218      * Get all policies that are tracked by this table.
219      *
220      * @param shouldContainQosChars Whether the returned policies should contain QosCharacteristics.
221      *                              Only applicable if SDK >= V.
222      * @return List of policies, or empty list if there are no policies in the table.
223      */
getAllPolicies(boolean shouldContainQosChars)224     public List<QosPolicyParams> getAllPolicies(boolean shouldContainQosChars) {
225         if (mPolicyHashToPolicyMap.isEmpty()) {
226             return new ArrayList<>();
227         }
228         Stream<QosPolicyParams> policyStream = mPolicyHashToPolicyMap.values().stream();
229         if (SdkLevel.isAtLeastV()) {
230             policyStream = policyStream.filter(p ->
231                     shouldContainQosChars == (p.getQosCharacteristics() != null));
232         }
233         return policyStream.toList();
234     }
235 
236     /**
237      * Dump information about the internal state.
238      *
239      * @param pw PrintWriter to write the dump to.
240      */
dump(PrintWriter pw)241     public void dump(PrintWriter pw) {
242         pw.println("Dump of ApplicationQosPolicyTrackingTable");
243         int numAvailableVirtualPolicyIds = mAvailableVirtualPolicyIds.size();
244         int numTrackedPolicies = mPolicyHashToPolicyMap.size();
245         pw.println("Total table size: " + (numAvailableVirtualPolicyIds + numTrackedPolicies));
246         pw.println("Num available virtual policy IDs: " + numAvailableVirtualPolicyIds);
247         pw.println("Num tracked policies: " + numTrackedPolicies);
248         pw.println();
249 
250         pw.println("Available virtual policy IDs: " + mAvailableVirtualPolicyIds);
251         pw.println("Tracked policies:");
252         for (Map.Entry<Long, QosPolicyParams> entry : mPolicyHashToPolicyMap.entrySet()) {
253             long policyHash = entry.getKey();
254             pw.println("  Policy ID: " + getPolicyIdFromCombinedLong(policyHash));
255             pw.println("  Requester UID: " + getUidFromCombinedLong(policyHash));
256             pw.println(entry.getValue());
257         }
258         pw.println();
259     }
260 }
261