1 /* 2 * Copyright (C) 2022 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.connectivity; 18 19 import android.annotation.NonNull; 20 import android.net.UidRange; 21 import android.util.ArraySet; 22 23 import java.util.ArrayList; 24 import java.util.Arrays; 25 import java.util.Collections; 26 import java.util.List; 27 import java.util.Objects; 28 import java.util.Set; 29 30 /** 31 * Utility class for UidRange 32 * 33 * @hide 34 */ 35 public final class UidRangeUtils { 36 /** 37 * Check if given uid range set is within the uid range 38 * @param uids uid range in which uidRangeSet is checked to be in range. 39 * @param uidRangeSet uid range set to be be checked if it is in range of uids 40 * @return true uidRangeSet is in the range of uids 41 * @hide 42 */ isRangeSetInUidRange(@onNull UidRange uids, @NonNull Set<UidRange> uidRangeSet)43 public static boolean isRangeSetInUidRange(@NonNull UidRange uids, 44 @NonNull Set<UidRange> uidRangeSet) { 45 Objects.requireNonNull(uids); 46 Objects.requireNonNull(uidRangeSet); 47 if (uidRangeSet.size() == 0) { 48 return true; 49 } 50 for (UidRange range : uidRangeSet) { 51 if (!uids.contains(range.start) || !uids.contains(range.stop)) { 52 return false; 53 } 54 } 55 return true; 56 } 57 58 /** 59 * Remove given uid ranges set from a uid range 60 * @param uids uid range from which uidRangeSet will be removed 61 * @param uidRangeSet uid range set to be removed from uids. 62 * WARNING : This function requires the UidRanges in uidRangeSet to be disjoint 63 * WARNING : This function requires the arrayset to be iterated in increasing order of the 64 * ranges. Today this is provided by the iteration order stability of 65 * ArraySet, and the fact that the code creating this ArraySet always 66 * creates it in increasing order. 67 * Note : if any of the above is not satisfied this function throws IllegalArgumentException 68 * TODO : remove these limitations 69 * @hide 70 */ removeRangeSetFromUidRange(@onNull UidRange uids, @NonNull ArraySet<UidRange> uidRangeSet)71 public static ArraySet<UidRange> removeRangeSetFromUidRange(@NonNull UidRange uids, 72 @NonNull ArraySet<UidRange> uidRangeSet) { 73 Objects.requireNonNull(uids); 74 Objects.requireNonNull(uidRangeSet); 75 final ArraySet<UidRange> filteredRangeSet = new ArraySet<UidRange>(); 76 if (uidRangeSet.size() == 0) { 77 filteredRangeSet.add(uids); 78 return filteredRangeSet; 79 } 80 81 int start = uids.start; 82 UidRange previousRange = null; 83 for (UidRange uidRange : uidRangeSet) { 84 if (previousRange != null) { 85 if (previousRange.stop > uidRange.start) { 86 throw new IllegalArgumentException("UID ranges are not increasing order"); 87 } 88 } 89 if (uidRange.start > start) { 90 filteredRangeSet.add(new UidRange(start, uidRange.start - 1)); 91 start = uidRange.stop + 1; 92 } else if (uidRange.start == start) { 93 start = uidRange.stop + 1; 94 } 95 previousRange = uidRange; 96 } 97 if (start < uids.stop) { 98 filteredRangeSet.add(new UidRange(start, uids.stop)); 99 } 100 return filteredRangeSet; 101 } 102 103 /** 104 * Compare if the given UID range sets have overlapping uids 105 * @param uidRangeSet1 first uid range set to check for overlap 106 * @param uidRangeSet2 second uid range set to check for overlap 107 * @hide 108 */ doesRangeSetOverlap(@onNull Set<UidRange> uidRangeSet1, @NonNull Set<UidRange> uidRangeSet2)109 public static boolean doesRangeSetOverlap(@NonNull Set<UidRange> uidRangeSet1, 110 @NonNull Set<UidRange> uidRangeSet2) { 111 Objects.requireNonNull(uidRangeSet1); 112 Objects.requireNonNull(uidRangeSet2); 113 114 if (uidRangeSet1.size() == 0 || uidRangeSet2.size() == 0) { 115 return false; 116 } 117 for (UidRange range1 : uidRangeSet1) { 118 for (UidRange range2 : uidRangeSet2) { 119 if (range1.contains(range2.start) || range1.contains(range2.stop) 120 || range2.contains(range1.start) || range2.contains(range1.stop)) { 121 return true; 122 } 123 } 124 } 125 return false; 126 } 127 128 /** 129 * Convert a list of uids to set of UidRanges. 130 * @param uids list of uids 131 * @return set of UidRanges 132 * @hide 133 */ convertListToUidRange(@onNull List<Integer> uids)134 public static ArraySet<UidRange> convertListToUidRange(@NonNull List<Integer> uids) { 135 Objects.requireNonNull(uids); 136 final ArraySet<UidRange> uidRangeSet = new ArraySet<UidRange>(); 137 if (uids.size() == 0) { 138 return uidRangeSet; 139 } 140 List<Integer> uidsNew = new ArrayList<>(uids); 141 Collections.sort(uidsNew); 142 int start = uidsNew.get(0); 143 int stop = start; 144 145 for (Integer i : uidsNew) { 146 if (i <= stop + 1) { 147 stop = i; 148 } else { 149 uidRangeSet.add(new UidRange(start, stop)); 150 start = i; 151 stop = i; 152 } 153 } 154 uidRangeSet.add(new UidRange(start, stop)); 155 return uidRangeSet; 156 } 157 158 /** 159 * Convert an array of uids to set of UidRanges. 160 * @param uids array of uids 161 * @return set of UidRanges 162 * @hide 163 */ convertArrayToUidRange(@onNull int[] uids)164 public static ArraySet<UidRange> convertArrayToUidRange(@NonNull int[] uids) { 165 Objects.requireNonNull(uids); 166 final ArraySet<UidRange> uidRangeSet = new ArraySet<UidRange>(); 167 if (uids.length == 0) { 168 return uidRangeSet; 169 } 170 int[] uidsNew = uids.clone(); 171 Arrays.sort(uidsNew); 172 int start = uidsNew[0]; 173 int stop = start; 174 175 for (int i : uidsNew) { 176 if (i <= stop + 1) { 177 stop = i; 178 } else { 179 uidRangeSet.add(new UidRange(start, stop)); 180 start = i; 181 stop = i; 182 } 183 } 184 uidRangeSet.add(new UidRange(start, stop)); 185 return uidRangeSet; 186 } 187 compare(UidRange range1, UidRange range2)188 private static int compare(UidRange range1, UidRange range2) { 189 return range1.start - range2.start; 190 } 191 192 /** 193 * Sort the given UidRange array. 194 * 195 * @param ranges The array of UidRange which is going to be sorted. 196 * @return Array of UidRange. 197 */ sortRangesByStartUid(UidRange[] ranges)198 public static UidRange[] sortRangesByStartUid(UidRange[] ranges) { 199 final ArrayList uidRanges = new ArrayList(Arrays.asList(ranges)); 200 Collections.sort(uidRanges, UidRangeUtils::compare); 201 return (UidRange[]) uidRanges.toArray(new UidRange[0]); 202 } 203 204 /** 205 * Check if the given sorted UidRange array contains overlap or not. 206 * 207 * Note that the sorted UidRange array must be sorted by increasing lower bound. If it's not, 208 * the behavior is undefined. 209 * 210 * @param ranges The sorted UidRange array which is going to be checked if there is an overlap 211 * or not. 212 * @return A boolean to indicate if the given sorted UidRange array contains overlap or not. 213 */ sortedRangesContainOverlap(UidRange[] ranges)214 public static boolean sortedRangesContainOverlap(UidRange[] ranges) { 215 final ArrayList uidRanges = new ArrayList(Arrays.asList(ranges)); 216 for (int i = 0; i + 1 < uidRanges.size(); i++) { 217 if (((UidRange) uidRanges.get(i + 1)).start <= ((UidRange) uidRanges.get(i)).stop) { 218 return true; 219 } 220 } 221 222 return false; 223 } 224 } 225