1 /*
2 * Copyright (C) 2018 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 #pragma once
17
18 #include "src/statsd_config.pb.h"
19 #include "annotations.h"
20
21 namespace android {
22 namespace os {
23 namespace statsd {
24
25 class HashableDimensionKey;
26 struct Matcher;
27 struct Field;
28 struct FieldValue;
29
30 const int32_t kMaxLogDepth = 2;
31 const int32_t kLastBitMask = 0x80;
32 const int32_t kClearLastBitDeco = 0x7f;
33 const int32_t kClearAllPositionMatcherMask = 0xffff00ff;
34
35 enum Type { UNKNOWN, INT, LONG, FLOAT, DOUBLE, STRING, STORAGE };
36
37 int32_t getEncodedField(int32_t pos[], int32_t depth, bool includeDepth);
38
39 int32_t encodeMatcherMask(int32_t mask[], int32_t depth);
40
41 // Get the encoded field for a leaf with a [field] number at depth 0;
getSimpleField(size_t field)42 inline int32_t getSimpleField(size_t field) {
43 return ((int32_t)field << 8 * 2);
44 }
45
46 /**
47 * Field is a wrapper class for 2 integers that represents the field of a log element in its Atom
48 * proto.
49 * [mTag]: the atom id.
50 * [mField]: encoded path from the root (atom) to leaf.
51 *
52 * For example:
53 * WakeLockStateChanged {
54 * repeated AttributionNode = 1;
55 * int state = 2;
56 * string tag = 3;
57 * }
58 * Read from logd, the items are structured as below:
59 * [[[1000, "tag"], [2000, "tag2"],], 2,"hello"]
60 *
61 * When we read through the list, we will encode each field in a 32bit integer.
62 * 8bit segments |--------|--------|--------|--------|
63 * Depth field0 [L]field1 [L]field1
64 *
65 * The first 8 bits are the depth of the field. for example, the uid 1000 has depth 2.
66 * The following 3 8-bit are for the item's position at each level.
67 * The first bit of each 8bits field is reserved to mark if the item is the last item at that level
68 * this is to make matching easier later.
69 *
70 * The above wakelock event is translated into FieldValue pairs.
71 * 0x02010101->1000
72 * 0x02010182->tag
73 * 0x02018201->2000
74 * 0x02018282->tag2
75 * 0x00020000->2
76 * 0x00030000->"hello"
77 *
78 * This encoding is the building block for the later operations.
79 * Please see the definition for Matcher below to see how the matching is done.
80 */
81 struct Field {
82 private:
83 int32_t mTag;
84 int32_t mField;
85
86 public:
FieldField87 Field() {}
88
FieldField89 Field(int32_t tag, int32_t pos[], int32_t depth) : mTag(tag) {
90 mField = getEncodedField(pos, depth, true);
91 }
92
FieldField93 Field(const Field& from) : mTag(from.getTag()), mField(from.getField()) {
94 }
95
FieldField96 Field(int32_t tag, int32_t field) : mTag(tag), mField(field){};
97
setFieldField98 inline void setField(int32_t field) {
99 mField = field;
100 }
101
setTagField102 inline void setTag(int32_t tag) {
103 mTag = tag;
104 }
105
decorateLastPosField106 inline void decorateLastPos(int32_t depth) {
107 int32_t mask = kLastBitMask << 8 * (kMaxLogDepth - depth);
108 mField |= mask;
109 }
110
getTagField111 inline int32_t getTag() const {
112 return mTag;
113 }
114
getDepthField115 inline int32_t getDepth() const {
116 return (mField >> 24);
117 }
118
getPathField119 inline int32_t getPath(int32_t depth) const {
120 if (depth > 2 || depth < 0) return 0;
121
122 int32_t field = (mField & 0x00ffffff);
123 int32_t mask = 0xffffffff;
124 return (field & (mask << 8 * (kMaxLogDepth - depth)));
125 }
126
getPrefixField127 inline int32_t getPrefix(int32_t depth) const {
128 if (depth == 0) return 0;
129 return getPath(depth - 1);
130 }
131
getFieldField132 inline int32_t getField() const {
133 return mField;
134 }
135
getRawPosAtDepthField136 inline int32_t getRawPosAtDepth(int32_t depth) const {
137 int32_t field = (mField & 0x00ffffff);
138 int32_t shift = 8 * (kMaxLogDepth - depth);
139 int32_t mask = 0xff << shift;
140
141 return (field & mask) >> shift;
142 }
143
getPosAtDepthField144 inline int32_t getPosAtDepth(int32_t depth) const {
145 return getRawPosAtDepth(depth) & kClearLastBitDeco;
146 }
147
148 // Check if the first bit of the 8-bit segment for depth is 1
isLastPosField149 inline bool isLastPos(int32_t depth) const {
150 int32_t field = (mField & 0x00ffffff);
151 int32_t mask = kLastBitMask << 8 * (kMaxLogDepth - depth);
152 return (field & mask) != 0;
153 }
154
155 // if the 8-bit segment is all 0's
isAnyPosMatcherField156 inline bool isAnyPosMatcher(int32_t depth) const {
157 return getDepth() >= depth && getRawPosAtDepth(depth) == 0;
158 }
159 // if the 8bit is 0x80 (1000 0000)
isLastPosMatcherField160 inline bool isLastPosMatcher(int32_t depth) const {
161 return getDepth() >= depth && getRawPosAtDepth(depth) == kLastBitMask;
162 }
163
164 inline bool operator==(const Field& that) const {
165 return mTag == that.getTag() && mField == that.getField();
166 };
167
168 inline bool operator!=(const Field& that) const {
169 return mTag != that.getTag() || mField != that.getField();
170 };
171
172 bool operator<(const Field& that) const {
173 if (mTag != that.getTag()) {
174 return mTag < that.getTag();
175 }
176
177 if (mField != that.getField()) {
178 return mField < that.getField();
179 }
180
181 return false;
182 }
183
184 bool matches(const Matcher& that) const;
185 };
186
187 /**
188 * Matcher represents a leaf matcher in the FieldMatcher in statsd_config.
189 *
190 * It contains all information needed to match one or more leaf node.
191 * All information is encoded in a Field(2 ints) and a bit mask(1 int).
192 *
193 * For example, to match the first/any/last uid field in attribution chain in Atom 10,
194 * we have the following FieldMatcher in statsd_config
195 * FieldMatcher {
196 * field:10
197 * FieldMatcher {
198 * field:1
199 * position: any/last/first
200 * FieldMatcher {
201 * field:1
202 * }
203 * }
204 * }
205 *
206 * We translate the FieldMatcher into a Field, and mask
207 * First: [Matcher Field] 0x02010101 [Mask]0xff7f7f7f
208 * Last: [Matcher Field] 0x02018001 [Mask]0xff7f807f
209 * Any: [Matcher Field] 0x02010001 [Mask]0xff7f007f
210 * All: [Matcher Field] 0x02010001 [Mask]0xff7f7f7f
211 *
212 * [To match a log Field with a Matcher] we apply the bit mask to the log Field and check if
213 * the result is equal to the Matcher Field. That's a bit wise AND operation + check if 2 ints are
214 * equal. Nothing can beat the performance of this matching algorithm.
215 *
216 * TODO(b/110561213): ADD EXAMPLE HERE.
217 */
218 struct Matcher {
MatcherMatcher219 Matcher(const Field& matcher, int32_t mask) : mMatcher(matcher), mMask(mask){};
220
221 const Field mMatcher;
222 const int32_t mMask;
223
getMatcherMatcher224 inline const Field& getMatcher() const {
225 return mMatcher;
226 }
227
getMaskMatcher228 inline int32_t getMask() const {
229 return mMask;
230 }
231
getRawMaskAtDepthMatcher232 inline int32_t getRawMaskAtDepth(int32_t depth) const {
233 int32_t field = (mMask & 0x00ffffff);
234 int32_t shift = 8 * (kMaxLogDepth - depth);
235 int32_t mask = 0xff << shift;
236
237 return (field & mask) >> shift;
238 }
239
hasAllPositionMatcherMatcher240 bool hasAllPositionMatcher() const {
241 return mMatcher.getDepth() == 2 && getRawMaskAtDepth(1) == 0x7f;
242 }
243
hasAnyPositionMatcherMatcher244 bool hasAnyPositionMatcher(int* prefix) const {
245 if (mMatcher.getDepth() == 2 && mMatcher.getRawPosAtDepth(1) == 0) {
246 (*prefix) = mMatcher.getPrefix(1);
247 return true;
248 }
249 return false;
250 }
251
252 inline bool operator!=(const Matcher& that) const {
253 return mMatcher != that.getMatcher() || mMask != that.getMask();
254 }
255
256 inline bool operator==(const Matcher& that) const {
257 return mMatcher == that.mMatcher && mMask == that.mMask;
258 }
259 };
260
getSimpleMatcher(int32_t tag,size_t field)261 inline Matcher getSimpleMatcher(int32_t tag, size_t field) {
262 return Matcher(Field(tag, getSimpleField(field)), 0xff7f0000);
263 }
264
getFirstUidMatcher(int32_t atomId)265 inline Matcher getFirstUidMatcher(int32_t atomId) {
266 int32_t pos[] = {1, 1, 1};
267 return Matcher(Field(atomId, pos, 2), 0xff7f7f7f);
268 }
269
270 /**
271 * A wrapper for a union type to contain multiple types of values.
272 *
273 */
274 struct Value {
ValueValue275 Value() : type(UNKNOWN) {}
276
ValueValue277 Value(int32_t v) {
278 int_value = v;
279 type = INT;
280 }
281
ValueValue282 Value(int64_t v) {
283 long_value = v;
284 type = LONG;
285 }
286
ValueValue287 Value(float v) {
288 float_value = v;
289 type = FLOAT;
290 }
291
ValueValue292 Value(double v) {
293 double_value = v;
294 type = DOUBLE;
295 }
296
ValueValue297 Value(const std::string& v) {
298 str_value = v;
299 type = STRING;
300 }
301
ValueValue302 Value(const std::vector<uint8_t>& v) {
303 storage_value = v;
304 type = STORAGE;
305 }
306
setIntValue307 void setInt(int32_t v) {
308 int_value = v;
309 type = INT;
310 }
311
setLongValue312 void setLong(int64_t v) {
313 long_value = v;
314 type = LONG;
315 }
316
setFloatValue317 void setFloat(float v) {
318 float_value = v;
319 type = FLOAT;
320 }
321
setDoubleValue322 void setDouble(double v) {
323 double_value = v;
324 type = DOUBLE;
325 }
326
327 union {
328 int32_t int_value;
329 int64_t long_value;
330 float float_value;
331 double double_value;
332 };
333 std::string str_value;
334 std::vector<uint8_t> storage_value;
335
336 Type type;
337
338 std::string toString() const;
339
340 bool isZero() const;
341
getTypeValue342 Type getType() const {
343 return type;
344 }
345
346 double getDouble() const;
347
348 Value(const Value& from);
349
350 bool operator==(const Value& that) const;
351 bool operator!=(const Value& that) const;
352
353 bool operator<(const Value& that) const;
354 bool operator>(const Value& that) const;
355 bool operator>=(const Value& that) const;
356 Value operator-(const Value& that) const;
357 Value& operator+=(const Value& that);
358 Value& operator=(const Value& that);
359 };
360
361 class Annotations {
362 public:
Annotations()363 Annotations() {
364 setNested(true); // Nested = true by default
365 }
366
367 // This enum stores where particular annotations can be found in the
368 // bitmask. Note that these pos do not correspond to annotation ids.
369 enum {
370 NESTED_POS = 0x0,
371 PRIMARY_POS = 0x1,
372 EXCLUSIVE_POS = 0x2,
373 UID_POS = 0x3
374 };
375
setNested(bool nested)376 inline void setNested(bool nested) { setBitmaskAtPos(NESTED_POS, nested); }
377
setPrimaryField(bool primary)378 inline void setPrimaryField(bool primary) { setBitmaskAtPos(PRIMARY_POS, primary); }
379
setExclusiveState(bool exclusive)380 inline void setExclusiveState(bool exclusive) { setBitmaskAtPos(EXCLUSIVE_POS, exclusive); }
381
setUidField(bool isUid)382 inline void setUidField(bool isUid) { setBitmaskAtPos(UID_POS, isUid); }
383
384 // Default value = false
isNested()385 inline bool isNested() const { return getValueFromBitmask(NESTED_POS); }
386
387 // Default value = false
isPrimaryField()388 inline bool isPrimaryField() const { return getValueFromBitmask(PRIMARY_POS); }
389
390 // Default value = false
isExclusiveState()391 inline bool isExclusiveState() const { return getValueFromBitmask(EXCLUSIVE_POS); }
392
393 // Default value = false
isUidField()394 inline bool isUidField() const { return getValueFromBitmask(UID_POS); }
395
396 private:
setBitmaskAtPos(int pos,bool value)397 inline void setBitmaskAtPos(int pos, bool value) {
398 mBooleanBitmask &= ~(1 << pos); // clear
399 mBooleanBitmask |= (value << pos); // set
400 }
401
getValueFromBitmask(int pos)402 inline bool getValueFromBitmask(int pos) const {
403 return (mBooleanBitmask >> pos) & 0x1;
404 }
405
406 // This is a bitmask over all annotations stored in boolean form. Because
407 // there are only 4 booleans, just one byte is required.
408 uint8_t mBooleanBitmask = 0;
409 };
410
411 /**
412 * Represents a log item, or a dimension item (They are essentially the same).
413 */
414 struct FieldValue {
FieldValueFieldValue415 FieldValue() {}
FieldValueFieldValue416 FieldValue(const Field& field, const Value& value) : mField(field), mValue(value) {
417 }
418 bool operator==(const FieldValue& that) const {
419 return mField == that.mField && mValue == that.mValue;
420 }
421 bool operator!=(const FieldValue& that) const {
422 return mField != that.mField || mValue != that.mValue;
423 }
424 bool operator<(const FieldValue& that) const {
425 if (mField != that.mField) {
426 return mField < that.mField;
427 }
428
429 if (mValue != that.mValue) {
430 return mValue < that.mValue;
431 }
432
433 return false;
434 }
435
436 Field mField;
437 Value mValue;
438 Annotations mAnnotations;
439 };
440
441 bool HasPositionANY(const FieldMatcher& matcher);
442 bool HasPositionALL(const FieldMatcher& matcher);
443
444 bool isAttributionUidField(const FieldValue& value);
445
446 /* returns uid if the field is uid field, or -1 if the field is not a uid field */
447 int getUidIfExists(const FieldValue& value);
448
449 void translateFieldMatcher(const FieldMatcher& matcher, std::vector<Matcher>* output);
450
451 bool isAttributionUidField(const Field& field, const Value& value);
452 bool isUidField(const FieldValue& fieldValue);
453
454 bool equalDimensions(const std::vector<Matcher>& dimension_a,
455 const std::vector<Matcher>& dimension_b);
456
457 // Returns true if dimension_a is a subset of dimension_b.
458 bool subsetDimensions(const std::vector<Matcher>& dimension_a,
459 const std::vector<Matcher>& dimension_b);
460 } // namespace statsd
461 } // namespace os
462 } // namespace android
463