1/*
2 * Copyright (C) 2010 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.content;
18
19import android.os.SystemClock;
20import com.google.android.collect.Maps;
21
22import android.util.Pair;
23import android.util.Log;
24import android.accounts.Account;
25
26import java.util.HashMap;
27import java.util.ArrayList;
28import java.util.Map;
29import java.util.Iterator;
30
31/**
32 *
33 * @hide
34 */
35public class SyncQueue {
36    private static final String TAG = "SyncManager";
37    private SyncStorageEngine mSyncStorageEngine;
38
39    // A Map of SyncOperations operationKey -> SyncOperation that is designed for
40    // quick lookup of an enqueued SyncOperation.
41    private final HashMap<String, SyncOperation> mOperationsMap = Maps.newHashMap();
42
43    public SyncQueue(SyncStorageEngine syncStorageEngine) {
44        mSyncStorageEngine = syncStorageEngine;
45        ArrayList<SyncStorageEngine.PendingOperation> ops
46                = mSyncStorageEngine.getPendingOperations();
47        final int N = ops.size();
48        for (int i=0; i<N; i++) {
49            SyncStorageEngine.PendingOperation op = ops.get(i);
50            SyncOperation syncOperation = new SyncOperation(
51                    op.account, op.syncSource, op.authority, op.extras, 0 /* delay */);
52            syncOperation.expedited = op.expedited;
53            syncOperation.pendingOperation = op;
54            add(syncOperation, op);
55        }
56    }
57
58    public boolean add(SyncOperation operation) {
59        return add(operation, null /* this is not coming from the database */);
60    }
61
62    private boolean add(SyncOperation operation,
63            SyncStorageEngine.PendingOperation pop) {
64        // - if an operation with the same key exists and this one should run earlier,
65        //   update the earliestRunTime of the existing to the new time
66        // - if an operation with the same key exists and if this one should run
67        //   later, ignore it
68        // - if no operation exists then add the new one
69        final String operationKey = operation.key;
70        final SyncOperation existingOperation = mOperationsMap.get(operationKey);
71
72        if (existingOperation != null) {
73            boolean changed = false;
74            if (existingOperation.expedited == operation.expedited) {
75                final long newRunTime =
76                        Math.min(existingOperation.earliestRunTime, operation.earliestRunTime);
77                if (existingOperation.earliestRunTime != newRunTime) {
78                    existingOperation.earliestRunTime = newRunTime;
79                    changed = true;
80                }
81            } else {
82                if (operation.expedited) {
83                    existingOperation.expedited = true;
84                    changed = true;
85                }
86            }
87            return changed;
88        }
89
90        operation.pendingOperation = pop;
91        if (operation.pendingOperation == null) {
92            pop = new SyncStorageEngine.PendingOperation(
93                            operation.account, operation.syncSource,
94                            operation.authority, operation.extras, operation.expedited);
95            pop = mSyncStorageEngine.insertIntoPending(pop);
96            if (pop == null) {
97                throw new IllegalStateException("error adding pending sync operation "
98                        + operation);
99            }
100            operation.pendingOperation = pop;
101        }
102
103        mOperationsMap.put(operationKey, operation);
104        return true;
105    }
106
107    /**
108     * Remove the specified operation if it is in the queue.
109     * @param operation the operation to remove
110     */
111    public void remove(SyncOperation operation) {
112        SyncOperation operationToRemove = mOperationsMap.remove(operation.key);
113        if (operationToRemove == null) {
114            return;
115        }
116        if (!mSyncStorageEngine.deleteFromPending(operationToRemove.pendingOperation)) {
117            final String errorMessage = "unable to find pending row for " + operationToRemove;
118            Log.e(TAG, errorMessage, new IllegalStateException(errorMessage));
119        }
120    }
121
122    /**
123     * Find the operation that should run next. Operations are sorted by their earliestRunTime,
124     * prioritizing first those with a syncable state of "unknown" that aren't retries then
125     * expedited operations.
126     * The earliestRunTime is adjusted by the sync adapter's backoff and delayUntil times, if any.
127     * @return the operation that should run next and when it should run. The time may be in
128     * the future. It is expressed in milliseconds since boot.
129     */
130    public Pair<SyncOperation, Long> nextOperation() {
131        SyncOperation best = null;
132        long bestRunTime = 0;
133        boolean bestIsInitial = false;
134        for (SyncOperation op : mOperationsMap.values()) {
135            final long opRunTime = getOpTime(op);
136            final boolean opIsInitial = getIsInitial(op);
137            if (isOpBetter(best, bestRunTime, bestIsInitial, op, opRunTime, opIsInitial)) {
138                best = op;
139                bestIsInitial = opIsInitial;
140                bestRunTime = opRunTime;
141            }
142        }
143        if (best == null) {
144            return null;
145        }
146        return Pair.create(best, bestRunTime);
147    }
148
149    // VisibleForTesting
150    long getOpTime(SyncOperation op) {
151        long opRunTime = op.earliestRunTime;
152        if (!op.extras.getBoolean(ContentResolver.SYNC_EXTRAS_IGNORE_BACKOFF, false)) {
153            Pair<Long, Long> backoff = mSyncStorageEngine.getBackoff(op.account, op.authority);
154            long delayUntil = mSyncStorageEngine.getDelayUntilTime(op.account, op.authority);
155            opRunTime = Math.max(
156                    Math.max(opRunTime, delayUntil),
157                    backoff != null ? backoff.first : 0);
158        }
159        return opRunTime;
160    }
161
162    // VisibleForTesting
163    boolean getIsInitial(SyncOperation op) {
164        // Initial op is defined as an op with an unknown syncable that is not a retry.
165        // We know a sync is a retry if the intialization flag is set, since that will only
166        // be set by the sync dispatching code, thus if it is set it must have already been
167        // dispatched
168        return !op.extras.getBoolean(ContentResolver.SYNC_EXTRAS_INITIALIZE, false)
169        && mSyncStorageEngine.getIsSyncable(op.account, op.authority) < 0;
170    }
171
172    // return true if op is a better candidate than best. Rules:
173    // if the "Initial" state differs, make the current the best if it is "Initial".
174    // else, if the expedited state differs, pick the expedited unless it is backed off and the
175    // non-expedited isn't
176    // VisibleForTesting
177    boolean isOpBetter(
178            SyncOperation best, long bestRunTime, boolean bestIsInitial,
179            SyncOperation op, long opRunTime, boolean opIsInitial) {
180        boolean setBest = false;
181        if (Log.isLoggable(TAG, Log.VERBOSE)) {
182            Log.v(TAG,  "nextOperation: Processing op: " + op);
183        }
184        if (best == null) {
185            if (Log.isLoggable(TAG, Log.VERBOSE)) {
186                Log.v(TAG,  "   First op selected");
187            }
188            setBest = true;
189        } else if (bestIsInitial == opIsInitial) {
190            if (best.expedited == op.expedited) {
191                if (opRunTime < bestRunTime) {
192                    //  if both have same level, earlier time wins
193                    if (Log.isLoggable(TAG, Log.VERBOSE)) {
194                        Log.v(TAG,  "   Same expedite level - new op selected");
195                    }
196                    setBest = true;
197                }
198            } else {
199                final long now = SystemClock.elapsedRealtime();
200                if (op.expedited) {
201                    if (opRunTime <= now || bestRunTime > now) {
202                        // if op is expedited, it wins unless op can't run yet and best can
203                        if (Log.isLoggable(TAG, Log.VERBOSE)) {
204                            Log.v(TAG,  "   New op is expedited and can run - new op selected");
205                        }
206                        setBest = true;
207                    } else {
208                        if (Log.isLoggable(TAG, Log.VERBOSE)) {
209                            Log.v(TAG,  "   New op is expedited but can't run and best can");
210                        }
211                    }
212                } else {
213                    if (bestRunTime > now && opRunTime <= now) {
214                        // if best is expedited but can't run yet and op can run, op wins
215                        if (Log.isLoggable(TAG, Log.VERBOSE)) {
216                            Log.v(TAG,
217                                    "   New op is not expedited but can run - new op selected");
218                        }
219                        setBest = true;
220                    }
221                }
222            }
223        } else {
224            if (opIsInitial) {
225                if (Log.isLoggable(TAG, Log.VERBOSE)) {
226                    Log.v(TAG,  "   New op is init - new op selected");
227                }
228                setBest = true;
229            }
230        }
231        return setBest;
232    }
233
234    /**
235     * Find and return the SyncOperation that should be run next and is ready to run.
236     * @param now the current {@link android.os.SystemClock#elapsedRealtime()}, used to
237     * decide if the sync operation is ready to run
238     * @return the SyncOperation that should be run next and is ready to run.
239     */
240    public Pair<SyncOperation, Long> nextReadyToRun(long now) {
241        Pair<SyncOperation, Long> nextOpAndRunTime = nextOperation();
242        if (nextOpAndRunTime == null || nextOpAndRunTime.second > now) {
243            return null;
244        }
245        return nextOpAndRunTime;
246    }
247
248    public void remove(Account account, String authority) {
249        Iterator<Map.Entry<String, SyncOperation>> entries = mOperationsMap.entrySet().iterator();
250        while (entries.hasNext()) {
251            Map.Entry<String, SyncOperation> entry = entries.next();
252            SyncOperation syncOperation = entry.getValue();
253            if (account != null && !syncOperation.account.equals(account)) {
254                continue;
255            }
256            if (authority != null && !syncOperation.authority.equals(authority)) {
257                continue;
258            }
259            entries.remove();
260            if (!mSyncStorageEngine.deleteFromPending(syncOperation.pendingOperation)) {
261                final String errorMessage = "unable to find pending row for " + syncOperation;
262                Log.e(TAG, errorMessage, new IllegalStateException(errorMessage));
263            }
264        }
265    }
266
267    public void dump(StringBuilder sb) {
268        sb.append("SyncQueue: ").append(mOperationsMap.size()).append(" operation(s)\n");
269        for (SyncOperation operation : mOperationsMap.values()) {
270            sb.append(operation).append("\n");
271        }
272    }
273}
274