1// Copyright (C) 2018 The Android Open Source Project
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//      http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15import {assertExists, assertTrue} from '../base/logging';
16import {Engine} from '../common/engine';
17import {Registry} from '../common/registry';
18import {TraceTime, TrackState} from '../common/state';
19import {fromNs, toNs} from '../common/time';
20import {LIMIT, TrackData} from '../common/track_data';
21
22import {Controller} from './controller';
23import {ControllerFactory} from './controller';
24import {globals} from './globals';
25
26interface TrackConfig {}
27
28type TrackConfigWithNamespace = TrackConfig&{namespace: string};
29
30// Allow to override via devtools for testing (note, needs to be done in the
31// controller-thread).
32(self as {} as {quantPx: number}).quantPx = 1;
33
34// TrackController is a base class overridden by track implementations (e.g.,
35// sched slices, nestable slices, counters).
36export abstract class TrackController<
37    Config, Data extends TrackData = TrackData> extends Controller<'main'> {
38  readonly trackId: string;
39  readonly engine: Engine;
40  private data?: TrackData;
41  private requestingData = false;
42  private queuedRequest = false;
43  private isSetup = false;
44  private lastReloadHandled = 0;
45
46  // We choose 100000 as the table size to cache as this is roughly the point
47  // where SQLite sorts start to become expensive.
48  private static readonly MIN_TABLE_SIZE_TO_CACHE = 100000;
49
50  constructor(args: TrackControllerArgs) {
51    super('main');
52    this.trackId = args.trackId;
53    this.engine = args.engine;
54  }
55
56  protected pxSize(): number {
57    return (self as {} as {quantPx: number}).quantPx;
58  }
59
60  // Can be overriden by the track implementation to allow one time setup work
61  // to be performed before the first onBoundsChange invcation.
62  async onSetup() {}
63
64  // Can be overriden by the track implementation to allow some one-off work
65  // when requested reload (e.g. recalculating height).
66  async onReload() {}
67
68  // Must be overridden by the track implementation. Is invoked when the track
69  // frontend runs out of cached data. The derived track controller is expected
70  // to publish new track data in response to this call.
71  abstract async onBoundsChange(start: number, end: number, resolution: number):
72      Promise<Data>;
73
74  get trackState(): TrackState {
75    return assertExists(globals.state.tracks[this.trackId]);
76  }
77
78  get config(): Config {
79    return this.trackState.config as Config;
80  }
81
82  configHasNamespace(config: TrackConfig): config is TrackConfigWithNamespace {
83    return 'namespace' in config;
84  }
85
86  namespaceTable(tableName: string): string {
87    if (this.configHasNamespace(this.config)) {
88      return this.config.namespace + '_' + tableName;
89    } else {
90      return tableName;
91    }
92  }
93
94  publish(data: Data): void {
95    this.data = data;
96    globals.publish('TrackData', {id: this.trackId, data});
97  }
98
99  /**
100   * Returns a valid SQL table name with the given prefix that should be unique
101   * for each track.
102   */
103  tableName(prefix: string) {
104    // Derive table name from, since that is unique for each track.
105    // Track ID can be UUID but '-' is not valid for sql table name.
106    const idSuffix = this.trackId.split('-').join('_');
107    return `${prefix}_${idSuffix}`;
108  }
109
110  shouldSummarize(resolution: number): boolean {
111    // |resolution| is in s/px (to nearest power of 10) assuming a display
112    // of ~1000px 0.0008 is 0.8s.
113    return resolution >= 0.0008;
114  }
115
116  protected async query(query: string) {
117    const result = await this.engine.query(query);
118    return result;
119  }
120
121  private shouldReload(): boolean {
122    const {lastTrackReloadRequest} = globals.state;
123    return !!lastTrackReloadRequest &&
124        this.lastReloadHandled < lastTrackReloadRequest;
125  }
126
127  private markReloadHandled() {
128    this.lastReloadHandled = globals.state.lastTrackReloadRequest || 0;
129  }
130
131  shouldRequestData(traceTime: TraceTime): boolean {
132    if (this.data === undefined) return true;
133    if (this.shouldReload()) return true;
134
135    // If at the limit only request more data if the view has moved.
136    const atLimit = this.data.length === LIMIT;
137    if (atLimit) {
138      // We request more data than the window, so add window duration to find
139      // the previous window.
140      const prevWindowStart =
141          this.data.start + (traceTime.startSec - traceTime.endSec);
142      return traceTime.startSec !== prevWindowStart;
143    }
144
145    // Otherwise request more data only when out of range of current data or
146    // resolution has changed.
147    const inRange = traceTime.startSec >= this.data.start &&
148        traceTime.endSec <= this.data.end;
149    return !inRange ||
150        this.data.resolution !==
151        globals.state.frontendLocalState.visibleState.resolution;
152  }
153
154  // Decides, based on the the length of the trace and the number of rows
155  // provided whether a TrackController subclass should cache its quantized
156  // data. Returns the bucket size (in ns) if caching should happen and
157  // undefined otherwise.
158  // Subclasses should call this in their setup function
159  cachedBucketSizeNs(numRows: number): number|undefined {
160    // Ensure that we're not caching when the table size isn't even that big.
161    if (numRows < TrackController.MIN_TABLE_SIZE_TO_CACHE) {
162      return undefined;
163    }
164
165    const bounds = globals.state.traceTime;
166    const traceDurNs = toNs(bounds.endSec - bounds.startSec);
167
168    // For large traces, going through the raw table in the most zoomed-out
169    // states can be very expensive as this can involve going through O(millions
170    // of rows). The cost of this becomes high even for just iteration but is
171    // especially slow as quantization involves a SQLite sort on the quantized
172    // timestamp (for the group by).
173    //
174    // To get around this, we can cache a pre-quantized table which we can then
175    // in zoomed-out situations and fall back to the real table when zoomed in
176    // (which naturally constrains the amount of data by virtue of the window
177    // covering a smaller timespan)
178    //
179    // This method computes that cached table by computing an approximation for
180    // the bucket size we would use when totally zoomed out and then going a few
181    // resolution levels down which ensures that our cached table works for more
182    // than the literally most zoomed out state. Moving down a resolution level
183    // is defined as moving down a power of 2; this matches the logic in
184    // |globals.getCurResolution|.
185    //
186    // TODO(lalitm): in the future, we should consider having a whole set of
187    // quantized tables each of which cover some portion of resolution lvel
188    // range. As each table covers a large number of resolution levels, even 3-4
189    // tables should really cover the all concievable trace sizes. This set
190    // could be computed by looking at the number of events being processed one
191    // level below the cached table and computing another layer of caching if
192    // that count is too high (with respect to MIN_TABLE_SIZE_TO_CACHE).
193
194    // 4k monitors have 3840 horizontal pixels so use that for a worst case
195    // approximation of the window width.
196    const approxWidthPx = 3840;
197
198    // Compute the outermost bucket size. This acts as a starting point for
199    // computing the cached size.
200    const outermostResolutionLevel =
201        Math.ceil(Math.log2(traceDurNs / approxWidthPx));
202    const outermostBucketNs = Math.pow(2, outermostResolutionLevel);
203
204    // This constant decides how many resolution levels down from our outermost
205    // bucket computation we want to be able to use the cached table.
206    // We've chosen 7 as it seems to be empircally seems to be a good fit for
207    // trace data.
208    const resolutionLevelsCovered = 7;
209
210    // If we've got less resolution levels in the trace than the number of
211    // resolution levels we want to go down, bail out because this cached
212    // table is really not going to be used enough.
213    if (outermostResolutionLevel < resolutionLevelsCovered) {
214      return Number.MAX_SAFE_INTEGER;
215    }
216
217    // Another way to look at moving down resolution levels is to consider how
218    // many sub-intervals we are splitting the bucket into.
219    const bucketSubIntervals = Math.pow(2, resolutionLevelsCovered);
220
221    // Calculate the smallest bucket we want our table to be able to handle by
222    // dividing the outermsot bucket by the number of subintervals we should
223    // divide by.
224    const cachedBucketSizeNs = outermostBucketNs / bucketSubIntervals;
225
226    // Our logic above should make sure this is an integer but double check that
227    // here as an assertion before returning.
228    assertTrue(Number.isInteger(cachedBucketSizeNs));
229
230    return cachedBucketSizeNs;
231  }
232
233  run() {
234    const visibleState = globals.state.frontendLocalState.visibleState;
235    if (visibleState === undefined || visibleState.resolution === undefined ||
236        visibleState.resolution === Infinity) {
237      return;
238    }
239    const dur = visibleState.endSec - visibleState.startSec;
240    if (globals.state.visibleTracks.includes(this.trackId) &&
241        this.shouldRequestData(visibleState)) {
242      if (this.requestingData) {
243        this.queuedRequest = true;
244      } else {
245        this.requestingData = true;
246        let promise = Promise.resolve();
247        if (!this.isSetup) {
248          promise = this.onSetup();
249        } else if (this.shouldReload()) {
250          promise = this.onReload().then(() => this.markReloadHandled());
251        }
252        promise
253            .then(() => {
254              this.isSetup = true;
255              let resolution = visibleState.resolution;
256              // TODO(hjd): We shouldn't have to be so defensive here.
257              if (Math.log2(toNs(resolution)) % 1 !== 0) {
258                // resolution is in pixels per second so 1000 means
259                // 1px = 1ms.
260                resolution =
261                    fromNs(Math.pow(2, Math.floor(Math.log2(toNs(1000)))));
262              }
263              return this.onBoundsChange(
264                  visibleState.startSec - dur,
265                  visibleState.endSec + dur,
266                  resolution);
267            })
268            .then(data => {
269              this.publish(data);
270            })
271            .finally(() => {
272              this.requestingData = false;
273              if (this.queuedRequest) {
274                this.queuedRequest = false;
275                this.run();
276              }
277            });
278      }
279    }
280  }
281}
282
283export interface TrackControllerArgs {
284  trackId: string;
285  engine: Engine;
286}
287
288export interface TrackControllerFactory extends
289    ControllerFactory<TrackControllerArgs> {
290  kind: string;
291}
292
293export const trackControllerRegistry = new Registry<TrackControllerFactory>();
294