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
20 namespace android {
21 namespace os {
22 namespace statsd {
23
24 class HashableDimensionKey;
25 struct Matcher;
26 struct Field;
27 struct FieldValue;
28
29 const int32_t kMaxLogDepth = 2;
30 const int32_t kLastBitMask = 0x80;
31 const int32_t kClearLastBitDeco = 0x7f;
32 const int32_t kClearAllPositionMatcherMask = 0xffff00ff;
33
34 enum Type { UNKNOWN, INT, LONG, FLOAT, DOUBLE, STRING, STORAGE };
35
36 int32_t getEncodedField(int32_t pos[], int32_t depth, bool includeDepth);
37
38 int32_t encodeMatcherMask(int32_t mask[], int32_t depth);
39
40 // Get the encoded field for a leaf with a [field] number at depth 0;
getSimpleField(size_t field)41 inline int32_t getSimpleField(size_t field) {
42 return ((int32_t)field << 8 * 2);
43 }
44
45 /**
46 * Field is a wrapper class for 2 integers that represents the field of a log element in its Atom
47 * proto.
48 * [mTag]: the atom id.
49 * [mField]: encoded path from the root (atom) to leaf.
50 *
51 * For example:
52 * WakeLockStateChanged {
53 * repeated AttributionNode = 1;
54 * int state = 2;
55 * string tag = 3;
56 * }
57 * Read from logd, the items are structured as below:
58 * [[[1000, "tag"], [2000, "tag2"],], 2,"hello"]
59 *
60 * When we read through the list, we will encode each field in a 32bit integer.
61 * 8bit segments |--------|--------|--------|--------|
62 * Depth field0 [L]field1 [L]field1
63 *
64 * The first 8 bits are the depth of the field. for example, the uid 1000 has depth 2.
65 * The following 3 8-bit are for the item's position at each level.
66 * The first bit of each 8bits field is reserved to mark if the item is the last item at that level
67 * this is to make matching easier later.
68 *
69 * The above wakelock event is translated into FieldValue pairs.
70 * 0x02010101->1000
71 * 0x02010182->tag
72 * 0x02018201->2000
73 * 0x02018282->tag2
74 * 0x00020000->2
75 * 0x00030000->"hello"
76 *
77 * This encoding is the building block for the later operations.
78 * Please see the definition for Matcher below to see how the matching is done.
79 */
80 struct Field {
81 private:
82 int32_t mTag;
83 int32_t mField;
84
85 public:
FieldField86 Field() {}
87
FieldField88 Field(int32_t tag, int32_t pos[], int32_t depth) : mTag(tag) {
89 mField = getEncodedField(pos, depth, true);
90 }
91
FieldField92 Field(const Field& from) : mTag(from.getTag()), mField(from.getField()) {
93 }
94
FieldField95 Field(int32_t tag, int32_t field) : mTag(tag), mField(field){};
96
setFieldField97 inline void setField(int32_t field) {
98 mField = field;
99 }
100
setTagField101 inline void setTag(int32_t tag) {
102 mTag = tag;
103 }
104
decorateLastPosField105 inline void decorateLastPos(int32_t depth) {
106 int32_t mask = kLastBitMask << 8 * (kMaxLogDepth - depth);
107 mField |= mask;
108 }
109
getTagField110 inline int32_t getTag() const {
111 return mTag;
112 }
113
getDepthField114 inline int32_t getDepth() const {
115 return (mField >> 24);
116 }
117
getPathField118 inline int32_t getPath(int32_t depth) const {
119 if (depth > 2 || depth < 0) return 0;
120
121 int32_t field = (mField & 0x00ffffff);
122 int32_t mask = 0xffffffff;
123 return (field & (mask << 8 * (kMaxLogDepth - depth)));
124 }
125
getPrefixField126 inline int32_t getPrefix(int32_t depth) const {
127 if (depth == 0) return 0;
128 return getPath(depth - 1);
129 }
130
getFieldField131 inline int32_t getField() const {
132 return mField;
133 }
134
getRawPosAtDepthField135 inline int32_t getRawPosAtDepth(int32_t depth) const {
136 int32_t field = (mField & 0x00ffffff);
137 int32_t shift = 8 * (kMaxLogDepth - depth);
138 int32_t mask = 0xff << shift;
139
140 return (field & mask) >> shift;
141 }
142
getPosAtDepthField143 inline int32_t getPosAtDepth(int32_t depth) const {
144 return getRawPosAtDepth(depth) & kClearLastBitDeco;
145 }
146
147 // Check if the first bit of the 8-bit segment for depth is 1
isLastPosField148 inline bool isLastPos(int32_t depth) const {
149 int32_t field = (mField & 0x00ffffff);
150 int32_t mask = kLastBitMask << 8 * (kMaxLogDepth - depth);
151 return (field & mask) != 0;
152 }
153
154 // if the 8-bit segment is all 0's
isAnyPosMatcherField155 inline bool isAnyPosMatcher(int32_t depth) const {
156 return getDepth() >= depth && getRawPosAtDepth(depth) == 0;
157 }
158 // if the 8bit is 0x80 (1000 0000)
isLastPosMatcherField159 inline bool isLastPosMatcher(int32_t depth) const {
160 return getDepth() >= depth && getRawPosAtDepth(depth) == kLastBitMask;
161 }
162
getSizeField163 inline size_t getSize() const {
164 return sizeof(mField) + sizeof(mTag);
165 }
166
167 inline bool operator==(const Field& that) const {
168 return mTag == that.getTag() && mField == that.getField();
169 };
170
171 inline bool operator!=(const Field& that) const {
172 return mTag != that.getTag() || mField != that.getField();
173 };
174
175 bool operator<(const Field& that) const {
176 if (mTag != that.getTag()) {
177 return mTag < that.getTag();
178 }
179
180 if (mField != that.getField()) {
181 return mField < that.getField();
182 }
183
184 return false;
185 }
186
187 bool matches(const Matcher& that) const;
188 };
189
190 /**
191 * Matcher represents a leaf matcher in the FieldMatcher in statsd_config.
192 *
193 * It contains all information needed to match one or more leaf node.
194 * All information is encoded in a Field(2 ints) and a bit mask(1 int).
195 *
196 * For example, to match the first/all/last uid field in attribution chain in Atom 10,
197 * we have the following FieldMatcher in statsd_config
198 * FieldMatcher {
199 * field:10
200 * FieldMatcher {
201 * field:1
202 * position: all/last/first
203 * FieldMatcher {
204 * field:1
205 * }
206 * }
207 * }
208 *
209 * We translate the FieldMatcher into a Field, and mask
210 * First: [Matcher Field] 0x02010101 [Mask]0xff7f7f7f
211 * Last: [Matcher Field] 0x02018001 [Mask]0xff7f807f
212 * All: [Matcher Field] 0x02010001 [Mask]0xff7f7f7f
213 *
214 * [To match a log Field with a Matcher] we apply the bit mask to the log Field and check if
215 * the result is equal to the Matcher Field. That's a bit wise AND operation + check if 2 ints are
216 * equal. Nothing can beat the performance of this matching algorithm.
217 *
218 * TODO(b/110561213): ADD EXAMPLE HERE.
219 */
220 struct Matcher {
MatcherMatcher221 Matcher(const Field& matcher, int32_t mask) : mMatcher(matcher), mMask(mask){};
222
223 const Field mMatcher;
224 const int32_t mMask;
225
getMatcherMatcher226 inline const Field& getMatcher() const {
227 return mMatcher;
228 }
229
getMaskMatcher230 inline int32_t getMask() const {
231 return mMask;
232 }
233
getRawMaskAtDepthMatcher234 inline int32_t getRawMaskAtDepth(int32_t depth) const {
235 int32_t field = (mMask & 0x00ffffff);
236 int32_t shift = 8 * (kMaxLogDepth - depth);
237 int32_t mask = 0xff << shift;
238
239 return (field & mask) >> shift;
240 }
241
hasAllPositionMatcherMatcher242 bool hasAllPositionMatcher() const {
243 return mMatcher.getDepth() >= 1 && mMatcher.getRawPosAtDepth(1) == 0 &&
244 getRawMaskAtDepth(1) == 0x7f;
245 }
246
hasFirstPositionMatcherMatcher247 bool hasFirstPositionMatcher() const {
248 return mMatcher.getDepth() >= 1 && mMatcher.getRawPosAtDepth(1) == 1;
249 }
250
hasLastPositionMatcherMatcher251 bool hasLastPositionMatcher() const {
252 return mMatcher.getDepth() >= 1 && mMatcher.isLastPosMatcher(1);
253 }
254
isEqualWithoutPositionBitsMatcher255 bool isEqualWithoutPositionBits(const Matcher& that) const {
256 return ((mMatcher.getField() & kClearAllPositionMatcherMask) ==
257 (that.getMatcher().getField() & kClearAllPositionMatcherMask));
258 }
259
260 inline bool operator!=(const Matcher& that) const {
261 return mMatcher != that.getMatcher() || mMask != that.getMask();
262 }
263
264 inline bool operator==(const Matcher& that) const {
265 return mMatcher == that.mMatcher && mMask == that.mMask;
266 }
267 };
268
getSimpleMatcher(int32_t tag,size_t field)269 inline Matcher getSimpleMatcher(int32_t tag, size_t field) {
270 return Matcher(Field(tag, getSimpleField(field)), 0xff7f0000);
271 }
272
getFirstUidMatcher(int32_t atomId)273 inline Matcher getFirstUidMatcher(int32_t atomId) {
274 int32_t pos[] = {1, 1, 1};
275 return Matcher(Field(atomId, pos, 2), 0xff7f7f7f);
276 }
277
278 /**
279 * A wrapper for a union type to contain multiple types of values.
280 *
281 */
282 struct Value {
ValueValue283 Value() : type(UNKNOWN) {}
284
ValueValue285 Value(int32_t v) {
286 int_value = v;
287 type = INT;
288 }
289
ValueValue290 Value(int64_t v) {
291 long_value = v;
292 type = LONG;
293 }
294
ValueValue295 Value(float v) {
296 float_value = v;
297 type = FLOAT;
298 }
299
ValueValue300 Value(double v) {
301 double_value = v;
302 type = DOUBLE;
303 }
304
ValueValue305 Value(const std::string& v) {
306 str_value = v;
307 type = STRING;
308 }
309
ValueValue310 Value(const std::vector<uint8_t>& v) {
311 storage_value = v;
312 type = STORAGE;
313 }
314
setIntValue315 void setInt(int32_t v) {
316 int_value = v;
317 type = INT;
318 }
319
setLongValue320 void setLong(int64_t v) {
321 long_value = v;
322 type = LONG;
323 }
324
setFloatValue325 void setFloat(float v) {
326 float_value = v;
327 type = FLOAT;
328 }
329
setDoubleValue330 void setDouble(double v) {
331 double_value = v;
332 type = DOUBLE;
333 }
334
335 union {
336 int32_t int_value;
337 int64_t long_value;
338 float float_value;
339 double double_value;
340 };
341 std::string str_value;
342 std::vector<uint8_t> storage_value;
343
344 Type type;
345
346 std::string toString() const;
347
348 bool isZero() const;
349
getTypeValue350 Type getType() const {
351 return type;
352 }
353
354 double getDouble() const;
355
356 size_t getSize() const;
357
358 Value(const Value& from);
359
360 bool operator==(const Value& that) const;
361 bool operator!=(const Value& that) const;
362
363 bool operator<(const Value& that) const;
364 bool operator>(const Value& that) const;
365 bool operator>=(const Value& that) const;
366 Value operator-(const Value& that) const;
367 Value& operator+=(const Value& that);
368 Value& operator=(const Value& that);
369 };
370
371 class Annotations {
372 public:
Annotations()373 Annotations() {
374 }
375
376 // This enum stores where particular annotations can be found in the
377 // bitmask. Note that these pos do not correspond to annotation ids.
378 enum {
379 NESTED_POS = 0x0,
380 PRIMARY_POS = 0x1,
381 EXCLUSIVE_POS = 0x2,
382 UID_POS = 0x3
383 };
384
setNested(bool nested)385 inline void setNested(bool nested) { setBitmaskAtPos(NESTED_POS, nested); }
386
setPrimaryField(bool primary)387 inline void setPrimaryField(bool primary) { setBitmaskAtPos(PRIMARY_POS, primary); }
388
setExclusiveState(bool exclusive)389 inline void setExclusiveState(bool exclusive) { setBitmaskAtPos(EXCLUSIVE_POS, exclusive); }
390
setUidField(bool isUid)391 inline void setUidField(bool isUid) { setBitmaskAtPos(UID_POS, isUid); }
392
393 // Default value = false
isNested()394 inline bool isNested() const { return getValueFromBitmask(NESTED_POS); }
395
396 // Default value = false
isPrimaryField()397 inline bool isPrimaryField() const { return getValueFromBitmask(PRIMARY_POS); }
398
399 // Default value = false
isExclusiveState()400 inline bool isExclusiveState() const { return getValueFromBitmask(EXCLUSIVE_POS); }
401
402 // Default value = false
isUidField()403 inline bool isUidField() const { return getValueFromBitmask(UID_POS); }
404
405 std::string toString() const;
406
407 private:
setBitmaskAtPos(int pos,bool value)408 inline void setBitmaskAtPos(int pos, bool value) {
409 mBooleanBitmask &= ~(1 << pos); // clear
410 mBooleanBitmask |= (value << pos); // set
411 }
412
getValueFromBitmask(int pos)413 inline bool getValueFromBitmask(int pos) const {
414 return (mBooleanBitmask >> pos) & 0x1;
415 }
416
417 // This is a bitmask over all annotations stored in boolean form. Because
418 // there are only 4 booleans, just one byte is required.
419 uint8_t mBooleanBitmask = 0;
420 };
421
422 /**
423 * Represents a log item, or a dimension item (They are essentially the same).
424 */
425 struct FieldValue {
FieldValueFieldValue426 FieldValue() {}
FieldValueFieldValue427 FieldValue(const Field& field, const Value& value) : mField(field), mValue(value) {
428 }
429 bool operator==(const FieldValue& that) const {
430 return mField == that.mField && mValue == that.mValue;
431 }
432 bool operator!=(const FieldValue& that) const {
433 return mField != that.mField || mValue != that.mValue;
434 }
435 bool operator<(const FieldValue& that) const {
436 if (mField != that.mField) {
437 return mField < that.mField;
438 }
439
440 if (mValue != that.mValue) {
441 return mValue < that.mValue;
442 }
443
444 return false;
445 }
446
getSizeFieldValue447 size_t getSize() const {
448 return mField.getSize() + mValue.getSize();
449 }
450
getSizeV2FieldValue451 size_t getSizeV2() const {
452 return mValue.getSize();
453 }
454
455 Field mField;
456 Value mValue;
457 Annotations mAnnotations;
458 };
459
460 bool HasPositionANY(const FieldMatcher& matcher);
461 bool HasPositionALL(const FieldMatcher& matcher);
462 bool HasPrimitiveRepeatedField(const FieldMatcher& matcher);
463 bool ShouldUseNestedDimensions(const FieldMatcher& matcher);
464
465 bool isAttributionUidField(const FieldValue& value);
466
467 /* returns uid if the field is uid field, or -1 if the field is not a uid field */
468 int getUidIfExists(const FieldValue& value);
469
470 std::vector<Matcher> dedupFieldMatchers(const std::vector<Matcher>& fieldMatchers);
471
472 void translateFieldMatcher(const FieldMatcher& matcher, std::vector<Matcher>* output);
473
474 bool isAttributionUidField(const Field& field, const Value& value);
475 bool isUidField(const FieldValue& fieldValue);
476 bool isPrimitiveRepeatedField(const Field& field);
477
478 bool equalDimensions(const std::vector<Matcher>& dimension_a,
479 const std::vector<Matcher>& dimension_b);
480
481 // Returns true if dimension_a is a subset of dimension_b.
482 bool subsetDimensions(const std::vector<Matcher>& dimension_a,
483 const std::vector<Matcher>& dimension_b);
484
485 // Estimate the memory size of the FieldValues. This is different from sizeof(FieldValue) because
486 // the size is computed at runtime using the actual contents stored in the FieldValue.
487 size_t getSize(const std::vector<FieldValue>& fieldValues);
488
489 // Same as getSize but does not compute the size of Field.
490 size_t getFieldValuesSizeV2(const std::vector<FieldValue>& fieldValues);
491
492 bool shouldKeepSample(const FieldValue& sampleFieldValue, int shardOffset, int shardCount);
493
494 } // namespace statsd
495 } // namespace os
496 } // namespace android
497