1 /*
2  * Copyright (C) 2024 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.autofill;
18 
19 import static com.android.server.autofill.Helper.sDebug;
20 
21 import android.util.Slog;
22 import android.util.SparseArray;
23 
24 import java.util.concurrent.atomic.AtomicInteger;
25 import java.util.List;
26 import java.util.Random;
27 
28 // Helper class containing various methods to deal with FillRequest Ids.
29 // For authentication flows, there needs to be a way to know whether to retrieve the Fill
30 // Response from the primary provider or the secondary provider from the requestId. A simple
31 // way to achieve this is by assigning odd number request ids to secondary provider and
32 // even numbers to primary provider.
33 public class RequestId {
34     private AtomicInteger sIdCounter;
35 
36     // The minimum request id is 2 to avoid possible authentication issues.
37     static final int MIN_REQUEST_ID = 2;
38     // The maximum request id is 0x7FFF to make sure the 16th bit is 0.
39     // This is to make sure the authentication id is always positive.
40     static final int MAX_REQUEST_ID = 0x7FFF; // 32767
41 
42     // The maximum start id is made small to best avoid wrapping around.
43     static final int MAX_START_ID = 1000;
44     // The magic number is used to determine if a wrap has happened.
45     // The underlying assumption of MAGIC_NUMBER is that there can't be as many as MAGIC_NUMBER
46     // of fill requests in one session. so there can't be as many as MAGIC_NUMBER of fill requests
47     // getting dropped.
48     static final int MAGIC_NUMBER = 5000;
49 
50     static final int MIN_PRIMARY_REQUEST_ID = 2;
51     static final int MAX_PRIMARY_REQUEST_ID = 0x7FFE; // 32766
52 
53     static final int MIN_SECONDARY_REQUEST_ID = 3;
54     static final int MAX_SECONDARY_REQUEST_ID = 0x7FFF; // 32767
55 
56     private static final String TAG = "RequestId";
57 
58     // WARNING: This constructor should only be used for testing
RequestId(int startId)59     RequestId(int startId) {
60         if (startId < MIN_REQUEST_ID || startId > MAX_REQUEST_ID) {
61             throw new IllegalArgumentException("startId must be between " + MIN_REQUEST_ID +
62                                                    " and " + MAX_REQUEST_ID);
63         }
64         if (sDebug) {
65             Slog.d(TAG, "RequestId(int): startId= " + startId);
66         }
67         sIdCounter = new AtomicInteger(startId);
68     }
69 
70     // WARNING: This get method should only be used for testing
getRequestId()71     int getRequestId() {
72         return sIdCounter.get();
73     }
74 
RequestId()75     public RequestId() {
76         Random random = new Random();
77         int low = MIN_REQUEST_ID;
78         int high = MAX_START_ID + 1; // nextInt is exclusive on upper limit
79 
80         // Generate a random start request id that >= MIN_REQUEST_ID and <= MAX_START_ID
81         int startId = random.nextInt(high - low) + low;
82         if (sDebug) {
83             Slog.d(TAG, "RequestId(): startId= " + startId);
84         }
85         sIdCounter = new AtomicInteger(startId);
86     }
87 
88     // Given a list of request ids, find the index of the last request id.
89     // Note: Since the request id wraps around, the largest request id may not be
90     // the latest request id.
91     //
92     // @param requestIds List of request ids in ascending order with at least one element.
93     // @return Index of the last request id.
getLastRequestIdIndex(List<Integer> requestIds)94     public static int getLastRequestIdIndex(List<Integer> requestIds) {
95         // If there is only one request id, return index as 0.
96         if (requestIds.size() == 1) {
97             return 0;
98         }
99 
100         // We have to use a magical number to determine if a wrap has happened because
101         // the request id could be lost. The underlying assumption of MAGIC_NUMBER is that
102         // there can't be as many as MAGIC_NUMBER of fill requests in one session.
103         boolean wrapHasHappened = false;
104         int latestRequestIdIndex = -1;
105 
106         for (int i = 0; i < requestIds.size() - 1; i++) {
107             if (requestIds.get(i+1) - requestIds.get(i) > MAGIC_NUMBER) {
108                 wrapHasHappened = true;
109                 latestRequestIdIndex = i;
110                 break;
111             }
112         }
113 
114         // If there was no wrap, the last request index is the last index.
115         if (!wrapHasHappened) {
116             latestRequestIdIndex = requestIds.size() - 1;
117         }
118         if (sDebug) {
119             Slog.d(TAG, "getLastRequestIdIndex(): latestRequestIdIndex = " + latestRequestIdIndex);
120         }
121         return latestRequestIdIndex;
122     }
123 
nextId(boolean isSecondary)124     public int nextId(boolean isSecondary) {
125         // For authentication flows, there needs to be a way to know whether to retrieve the Fill
126         // Response from the primary provider or the secondary provider from the requestId. A simple
127         // way to achieve this is by assigning odd number request ids to secondary provider and
128         // even numbers to primary provider.
129         int requestId;
130 
131         do {
132             requestId = sIdCounter.incrementAndGet() % (MAX_REQUEST_ID + 1);
133             // Skip numbers smaller than MIN_REQUEST_ID to avoid possible authentication issue
134             if (requestId < MIN_REQUEST_ID) {
135                 requestId = MIN_REQUEST_ID;
136             }
137             sIdCounter.set(requestId);
138         } while (isSecondaryProvider(requestId) != isSecondary);
139         if (sDebug) {
140             Slog.d(TAG, "nextId(): requestId = " + requestId);
141         }
142         return requestId;
143     }
144 
isSecondaryProvider(int requestId)145     public static boolean isSecondaryProvider(int requestId) {
146         return requestId % 2 == 1;
147     }
148 }
149