1 /* 2 * Copyright (C) 2021 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.internal.telephony; 18 19 import android.annotation.IntRange; 20 import android.annotation.NonNull; 21 import android.os.SystemClock; 22 import android.util.LongArrayQueue; 23 24 import com.android.internal.annotations.VisibleForTesting; 25 26 /** 27 * Tracks whether an event occurs mNumOccurrences times within the time span mWindowSizeMillis. 28 * <p/> 29 * Stores all events in memory, use a small number of required occurrences when using. 30 */ 31 public class SlidingWindowEventCounter { 32 private final long mWindowSizeMillis; 33 private final int mNumOccurrences; 34 private final LongArrayQueue mTimestampQueueMillis; 35 SlidingWindowEventCounter(@ntRangefrom = 0) final long windowSizeMillis, @IntRange(from = 2) final int numOccurrences)36 public SlidingWindowEventCounter(@IntRange(from = 0) final long windowSizeMillis, 37 @IntRange(from = 2) final int numOccurrences) { 38 if (windowSizeMillis < 0) { 39 throw new IllegalArgumentException("windowSizeMillis must be greater or equal to 0"); 40 } 41 if (numOccurrences <= 1) { 42 throw new IllegalArgumentException("numOccurrences must be greater than 1"); 43 } 44 45 mWindowSizeMillis = windowSizeMillis; 46 mNumOccurrences = numOccurrences; 47 mTimestampQueueMillis = new LongArrayQueue(numOccurrences); 48 } 49 50 /** 51 * Increments the occurrence counter. 52 * 53 * Returns true if an event has occurred at least mNumOccurrences times within the 54 * time span mWindowSizeMillis. 55 */ addOccurrence()56 public synchronized boolean addOccurrence() { 57 return addOccurrence(SystemClock.elapsedRealtime()); 58 } 59 60 /** 61 * Increments the occurrence counter. 62 * 63 * Returns true if an event has occurred at least mNumOccurrences times within the 64 * time span mWindowSizeMillis. 65 * @param timestampMillis 66 */ addOccurrence(long timestampMillis)67 public synchronized boolean addOccurrence(long timestampMillis) { 68 mTimestampQueueMillis.addLast(timestampMillis); 69 if (mTimestampQueueMillis.size() > mNumOccurrences) { 70 mTimestampQueueMillis.removeFirst(); 71 } 72 return isInWindow(); 73 } 74 75 /** 76 * Returns true if the conditions is satisfied. 77 */ isInWindow()78 public synchronized boolean isInWindow() { 79 return (mTimestampQueueMillis.size() == mNumOccurrences) 80 && mTimestampQueueMillis.peekFirst() 81 + mWindowSizeMillis > mTimestampQueueMillis.peekLast(); 82 } 83 84 @VisibleForTesting getQueuedNumOccurrences()85 int getQueuedNumOccurrences() { 86 return mTimestampQueueMillis.size(); 87 } 88 89 /** 90 * @return the time span in ms of the sliding window. 91 */ getWindowSizeMillis()92 public synchronized long getWindowSizeMillis() { 93 return mWindowSizeMillis; 94 } 95 96 /** 97 * @return the least number of occurrences for {@link #isInWindow} to be true. 98 */ getNumOccurrences()99 public synchronized int getNumOccurrences() { 100 return mNumOccurrences; 101 } 102 103 /** 104 * Get the event frequency description. 105 * 106 * @return A string describing the anomaly event 107 */ getFrequencyString()108 public @NonNull String getFrequencyString() { 109 if (mWindowSizeMillis >= 1000L) { 110 return mNumOccurrences + " times within " + mWindowSizeMillis / 1000L + " seconds"; 111 } else { 112 return mNumOccurrences + " times within " + mWindowSizeMillis + "ms"; 113 } 114 } 115 116 @Override toString()117 public String toString() { 118 return String.format("SlidingWindowEventCounter=[windowSizeMillis=" + mWindowSizeMillis 119 + ", numOccurrences=" + mNumOccurrences 120 + ", timestampQueueMillis=" + mTimestampQueueMillis + "]"); 121 } 122 } 123