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 
17 #define STATSD_DEBUG false
18 #include "Log.h"
19 
20 #include "FieldValue.h"
21 
22 #include "HashableDimensionKey.h"
23 #include "hash.h"
24 #include "math.h"
25 
26 namespace android {
27 namespace os {
28 namespace statsd {
29 
getEncodedField(int32_t pos[],int32_t depth,bool includeDepth)30 int32_t getEncodedField(int32_t pos[], int32_t depth, bool includeDepth) {
31     int32_t field = 0;
32     for (int32_t i = 0; i <= depth; i++) {
33         int32_t shiftBits = 8 * (kMaxLogDepth - i);
34         field |= (pos[i] << shiftBits);
35     }
36 
37     if (includeDepth) {
38         field |= (depth << 24);
39     }
40     return field;
41 }
42 
encodeMatcherMask(int32_t mask[],int32_t depth)43 int32_t encodeMatcherMask(int32_t mask[], int32_t depth) {
44     return getEncodedField(mask, depth, false) | 0xff000000;
45 }
46 
matches(const Matcher & matcher) const47 bool Field::matches(const Matcher& matcher) const {
48     if (mTag != matcher.mMatcher.getTag()) {
49         return false;
50     }
51     if ((mField & matcher.mMask) == matcher.mMatcher.getField()) {
52         return true;
53     }
54 
55     if (matcher.hasAllPositionMatcher() &&
56         (mField & (matcher.mMask & kClearAllPositionMatcherMask)) == matcher.mMatcher.getField()) {
57         return true;
58     }
59 
60     return false;
61 }
62 
dedupFieldMatchers(const std::vector<Matcher> & fieldMatchers)63 std::vector<Matcher> dedupFieldMatchers(const std::vector<Matcher>& fieldMatchers) {
64     std::vector<Matcher> dedupedFieldMatchers;
65     for (size_t i = 0; i < fieldMatchers.size(); i++) {
66         if (std::find(dedupedFieldMatchers.begin(), dedupedFieldMatchers.end(), fieldMatchers[i]) ==
67             dedupedFieldMatchers.end()) {
68             dedupedFieldMatchers.push_back(fieldMatchers[i]);
69         }
70     }
71     return dedupedFieldMatchers;
72 }
73 
translateFieldMatcher(int tag,const FieldMatcher & matcher,int depth,int * pos,int * mask,std::vector<Matcher> * output)74 void translateFieldMatcher(int tag, const FieldMatcher& matcher, int depth, int* pos, int* mask,
75                            std::vector<Matcher>* output) {
76     if (depth > kMaxLogDepth) {
77         ALOGE("depth > 2");
78         return;
79     }
80 
81     pos[depth] = matcher.field();
82     mask[depth] = 0x7f;
83 
84     if (matcher.has_position()) {
85         depth++;
86         if (depth > 2) {
87             return;
88         }
89         switch (matcher.position()) {
90             case Position::ALL:
91                 pos[depth] = 0x00;
92                 mask[depth] = 0x7f;
93                 break;
94             case Position::ANY:
95                 pos[depth] = 0;
96                 mask[depth] = 0;
97                 break;
98             case Position::FIRST:
99                 pos[depth] = 1;
100                 mask[depth] = 0x7f;
101                 break;
102             case Position::LAST:
103                 pos[depth] = 0x80;
104                 mask[depth] = 0x80;
105                 break;
106             case Position::POSITION_UNKNOWN:
107                 pos[depth] = 0;
108                 mask[depth] = 0;
109                 break;
110         }
111     }
112 
113     if (matcher.child_size() == 0) {
114         output->push_back(Matcher(Field(tag, pos, depth), encodeMatcherMask(mask, depth)));
115     } else {
116         for (const auto& child : matcher.child()) {
117             translateFieldMatcher(tag, child, depth + 1, pos, mask, output);
118         }
119     }
120 }
121 
translateFieldMatcher(const FieldMatcher & matcher,std::vector<Matcher> * output)122 void translateFieldMatcher(const FieldMatcher& matcher, std::vector<Matcher>* output) {
123     int pos[] = {1, 1, 1};
124     int mask[] = {0x7f, 0x7f, 0x7f};
125     int tag = matcher.field();
126     for (const auto& child : matcher.child()) {
127         translateFieldMatcher(tag, child, 0, pos, mask, output);
128     }
129 }
130 
isAttributionUidField(const FieldValue & value)131 bool isAttributionUidField(const FieldValue& value) {
132     return isAttributionUidField(value.mField, value.mValue);
133 }
134 
getUidIfExists(const FieldValue & value)135 int32_t getUidIfExists(const FieldValue& value) {
136     // the field is uid field if the field is the uid field in attribution node
137     // or annotated as such in the atom
138     bool isUid = isAttributionUidField(value) || isUidField(value);
139     return isUid ? value.mValue.int_value : -1;
140 }
141 
isAttributionUidField(const Field & field,const Value & value)142 bool isAttributionUidField(const Field& field, const Value& value) {
143     int f = field.getField() & 0xff007f;
144     if (f == 0x10001 && value.getType() == INT) {
145         return true;
146     }
147     return false;
148 }
149 
isUidField(const FieldValue & fieldValue)150 bool isUidField(const FieldValue& fieldValue) {
151     return fieldValue.mAnnotations.isUidField();
152 }
153 
isPrimitiveRepeatedField(const Field & field)154 bool isPrimitiveRepeatedField(const Field& field) {
155     return field.getDepth() == 1;
156 }
157 
Value(const Value & from)158 Value::Value(const Value& from) {
159     type = from.getType();
160     switch (type) {
161         case INT:
162             int_value = from.int_value;
163             break;
164         case LONG:
165             long_value = from.long_value;
166             break;
167         case FLOAT:
168             float_value = from.float_value;
169             break;
170         case DOUBLE:
171             double_value = from.double_value;
172             break;
173         case STRING:
174             str_value = from.str_value;
175             break;
176         case STORAGE:
177             storage_value = from.storage_value;
178             break;
179         default:
180             break;
181     }
182 }
183 
toString() const184 std::string Value::toString() const {
185     switch (type) {
186         case INT:
187             return std::to_string(int_value) + "[I]";
188         case LONG:
189             return std::to_string(long_value) + "[L]";
190         case FLOAT:
191             return std::to_string(float_value) + "[F]";
192         case DOUBLE:
193             return std::to_string(double_value) + "[D]";
194         case STRING:
195             return str_value + "[S]";
196         case STORAGE:
197             return "bytes of size " + std::to_string(storage_value.size()) + "[ST]";
198         default:
199             return "[UNKNOWN]";
200     }
201 }
202 
isZero() const203 bool Value::isZero() const {
204     switch (type) {
205         case INT:
206             return int_value == 0;
207         case LONG:
208             return long_value == 0;
209         case FLOAT:
210             return fabs(float_value) <= std::numeric_limits<float>::epsilon();
211         case DOUBLE:
212             return fabs(double_value) <= std::numeric_limits<double>::epsilon();
213         case STRING:
214             return str_value.size() == 0;
215         case STORAGE:
216             return storage_value.size() == 0;
217         default:
218             return false;
219     }
220 }
221 
operator ==(const Value & that) const222 bool Value::operator==(const Value& that) const {
223     if (type != that.getType()) return false;
224 
225     switch (type) {
226         case INT:
227             return int_value == that.int_value;
228         case LONG:
229             return long_value == that.long_value;
230         case FLOAT:
231             return float_value == that.float_value;
232         case DOUBLE:
233             return double_value == that.double_value;
234         case STRING:
235             return str_value == that.str_value;
236         case STORAGE:
237             return storage_value == that.storage_value;
238         default:
239             return false;
240     }
241 }
242 
operator !=(const Value & that) const243 bool Value::operator!=(const Value& that) const {
244     if (type != that.getType()) return true;
245     switch (type) {
246         case INT:
247             return int_value != that.int_value;
248         case LONG:
249             return long_value != that.long_value;
250         case FLOAT:
251             return float_value != that.float_value;
252         case DOUBLE:
253             return double_value != that.double_value;
254         case STRING:
255             return str_value != that.str_value;
256         case STORAGE:
257             return storage_value != that.storage_value;
258         default:
259             return false;
260     }
261 }
262 
operator <(const Value & that) const263 bool Value::operator<(const Value& that) const {
264     if (type != that.getType()) return type < that.getType();
265 
266     switch (type) {
267         case INT:
268             return int_value < that.int_value;
269         case LONG:
270             return long_value < that.long_value;
271         case FLOAT:
272             return float_value < that.float_value;
273         case DOUBLE:
274             return double_value < that.double_value;
275         case STRING:
276             return str_value < that.str_value;
277         case STORAGE:
278             return storage_value < that.storage_value;
279         default:
280             return false;
281     }
282 }
283 
operator >(const Value & that) const284 bool Value::operator>(const Value& that) const {
285     if (type != that.getType()) return type > that.getType();
286 
287     switch (type) {
288         case INT:
289             return int_value > that.int_value;
290         case LONG:
291             return long_value > that.long_value;
292         case FLOAT:
293             return float_value > that.float_value;
294         case DOUBLE:
295             return double_value > that.double_value;
296         case STRING:
297             return str_value > that.str_value;
298         case STORAGE:
299             return storage_value > that.storage_value;
300         default:
301             return false;
302     }
303 }
304 
operator >=(const Value & that) const305 bool Value::operator>=(const Value& that) const {
306     if (type != that.getType()) return type >= that.getType();
307 
308     switch (type) {
309         case INT:
310             return int_value >= that.int_value;
311         case LONG:
312             return long_value >= that.long_value;
313         case FLOAT:
314             return float_value >= that.float_value;
315         case DOUBLE:
316             return double_value >= that.double_value;
317         case STRING:
318             return str_value >= that.str_value;
319         case STORAGE:
320             return storage_value >= that.storage_value;
321         default:
322             return false;
323     }
324 }
325 
operator -(const Value & that) const326 Value Value::operator-(const Value& that) const {
327     Value v;
328     if (type != that.type) {
329         ALOGE("Can't operate on different value types, %d, %d", type, that.type);
330         return v;
331     }
332     if (type == STRING) {
333         ALOGE("Can't operate on string value type");
334         return v;
335     }
336 
337     if (type == STORAGE) {
338         ALOGE("Can't operate on storage value type");
339         return v;
340     }
341 
342     switch (type) {
343         case INT:
344             v.setInt(int_value - that.int_value);
345             break;
346         case LONG:
347             v.setLong(long_value - that.long_value);
348             break;
349         case FLOAT:
350             v.setFloat(float_value - that.float_value);
351             break;
352         case DOUBLE:
353             v.setDouble(double_value - that.double_value);
354             break;
355         default:
356             break;
357     }
358     return v;
359 }
360 
operator =(const Value & that)361 Value& Value::operator=(const Value& that) {
362     if (this != &that) {
363         type = that.type;
364         switch (type) {
365             case INT:
366                 int_value = that.int_value;
367                 break;
368             case LONG:
369                 long_value = that.long_value;
370                 break;
371             case FLOAT:
372                 float_value = that.float_value;
373                 break;
374             case DOUBLE:
375                 double_value = that.double_value;
376                 break;
377             case STRING:
378                 str_value = that.str_value;
379                 break;
380             case STORAGE:
381                 storage_value = that.storage_value;
382                 break;
383             default:
384                 break;
385         }
386     }
387     return *this;
388 }
389 
operator +=(const Value & that)390 Value& Value::operator+=(const Value& that) {
391     if (type != that.type) {
392         ALOGE("Can't operate on different value types, %d, %d", type, that.type);
393         return *this;
394     }
395     if (type == STRING) {
396         ALOGE("Can't operate on string value type");
397         return *this;
398     }
399     if (type == STORAGE) {
400         ALOGE("Can't operate on storage value type");
401         return *this;
402     }
403 
404     switch (type) {
405         case INT:
406             int_value += that.int_value;
407             break;
408         case LONG:
409             long_value += that.long_value;
410             break;
411         case FLOAT:
412             float_value += that.float_value;
413             break;
414         case DOUBLE:
415             double_value += that.double_value;
416             break;
417         default:
418             break;
419     }
420     return *this;
421 }
422 
getDouble() const423 double Value::getDouble() const {
424     switch (type) {
425         case INT:
426             return int_value;
427         case LONG:
428             return long_value;
429         case FLOAT:
430             return float_value;
431         case DOUBLE:
432             return double_value;
433         default:
434             return 0;
435     }
436 }
437 
getSize() const438 size_t Value::getSize() const {
439     size_t size = 0;
440     switch (type) {
441         case INT:
442             size = sizeof(int32_t);
443             break;
444         case LONG:
445             size = sizeof(int64_t);
446             break;
447         case FLOAT:
448             size = sizeof(float);
449             break;
450         case DOUBLE:
451             size = sizeof(double);
452             break;
453         case STRING:
454             size = sizeof(char) * str_value.length();
455             break;
456         case STORAGE:
457             size = sizeof(uint8_t) * storage_value.size();
458             break;
459         default:
460             break;
461     }
462     return size;
463 }
464 
toString() const465 std::string Annotations::toString() const {
466     std::string annotations;
467     if (isUidField()) {
468         annotations += "UID";
469     }
470     if (isPrimaryField()) {
471         annotations += annotations.size() > 0 ? ",PRIMARY" : "PRIMARY";
472     }
473     if (isExclusiveState()) {
474         annotations += annotations.size() > 0 ? ",EXCLUSIVE" : "EXCLUSIVE";
475     }
476     if (isNested()) {
477         annotations += annotations.size() > 0 ? ",NESTED" : "NESTED";
478     }
479     if (annotations.size()) {
480         annotations = "[" + annotations + "]";
481     }
482     return annotations;
483 }
484 
equalDimensions(const std::vector<Matcher> & dimension_a,const std::vector<Matcher> & dimension_b)485 bool equalDimensions(const std::vector<Matcher>& dimension_a,
486                      const std::vector<Matcher>& dimension_b) {
487     bool eq = dimension_a.size() == dimension_b.size();
488     for (size_t i = 0; eq && i < dimension_a.size(); ++i) {
489         if (dimension_b[i] != dimension_a[i]) {
490             eq = false;
491         }
492     }
493     return eq;
494 }
495 
496 /* Is dimension_a a subset of dimension_b. */
subsetDimensions(const std::vector<Matcher> & dimension_a,const std::vector<Matcher> & dimension_b)497 bool subsetDimensions(const std::vector<Matcher>& dimension_a,
498                       const std::vector<Matcher>& dimension_b) {
499     if (dimension_a.size() > dimension_b.size()) {
500         return false;
501     }
502     for (size_t i = 0; i < dimension_a.size(); ++i) {
503         bool found = false;
504         for (size_t j = 0; j < dimension_b.size(); ++j) {
505             if (dimension_a[i] == dimension_b[j]) {
506                 found = true;
507                 break;
508             }
509 
510             // Check equality of repeated fields with different positions.
511             // Only position FIRST and LAST are considered subsets of position ALL.
512             if (dimension_b[j].hasAllPositionMatcher() &&
513                 (dimension_a[i].hasFirstPositionMatcher() ||
514                  dimension_a[i].hasLastPositionMatcher())) {
515                 if (dimension_a[i].isEqualWithoutPositionBits(dimension_b[j])) {
516                     found = true;
517                     break;
518                 }
519             }
520         }
521         if (!found) {
522             return false;
523         }
524     }
525     return true;
526 }
527 
HasPositionANY(const FieldMatcher & matcher)528 bool HasPositionANY(const FieldMatcher& matcher) {
529     if (matcher.has_position() && matcher.position() == Position::ANY) {
530         return true;
531     }
532     for (const auto& child : matcher.child()) {
533         if (HasPositionANY(child)) {
534             return true;
535         }
536     }
537     return false;
538 }
539 
HasPositionALL(const FieldMatcher & matcher)540 bool HasPositionALL(const FieldMatcher& matcher) {
541     if (matcher.has_position() && matcher.position() == Position::ALL) {
542         return true;
543     }
544     for (const auto& child : matcher.child()) {
545         if (HasPositionALL(child)) {
546             return true;
547         }
548     }
549     return false;
550 }
551 
HasPrimitiveRepeatedField(const FieldMatcher & matcher)552 bool HasPrimitiveRepeatedField(const FieldMatcher& matcher) {
553     for (const auto& child : matcher.child()) {
554         if (child.has_position() && child.child_size() == 0) {
555             return true;
556         }
557     }
558     return false;
559 }
560 
ShouldUseNestedDimensions(const FieldMatcher & matcher)561 bool ShouldUseNestedDimensions(const FieldMatcher& matcher) {
562     return HasPositionALL(matcher) || HasPrimitiveRepeatedField(matcher);
563 }
564 
getSize(const std::vector<FieldValue> & fieldValues)565 size_t getSize(const std::vector<FieldValue>& fieldValues) {
566     size_t totalSize = 0;
567     for (const FieldValue& fieldValue : fieldValues) {
568         totalSize += fieldValue.getSize();
569     }
570     return totalSize;
571 }
572 
getFieldValuesSizeV2(const std::vector<FieldValue> & fieldValues)573 size_t getFieldValuesSizeV2(const std::vector<FieldValue>& fieldValues) {
574     size_t totalSize = 0;
575     for (const FieldValue& fieldValue : fieldValues) {
576         totalSize += fieldValue.getSizeV2();
577     }
578     return totalSize;
579 }
580 
shouldKeepSample(const FieldValue & sampleFieldValue,int shardOffset,int shardCount)581 bool shouldKeepSample(const FieldValue& sampleFieldValue, int shardOffset, int shardCount) {
582     int hashValue = 0;
583     switch (sampleFieldValue.mValue.type) {
584         case INT:
585             hashValue = Hash32(reinterpret_cast<const char*>(&sampleFieldValue.mValue.int_value),
586                                sizeof(sampleFieldValue.mValue.int_value));
587             break;
588         case LONG:
589             hashValue = Hash32(reinterpret_cast<const char*>(&sampleFieldValue.mValue.long_value),
590                                sizeof(sampleFieldValue.mValue.long_value));
591             break;
592         case FLOAT:
593             hashValue = Hash32(reinterpret_cast<const char*>(&sampleFieldValue.mValue.float_value),
594                                sizeof(sampleFieldValue.mValue.float_value));
595             break;
596         case DOUBLE:
597             hashValue = Hash32(reinterpret_cast<const char*>(&sampleFieldValue.mValue.double_value),
598                                sizeof(sampleFieldValue.mValue.double_value));
599             break;
600         case STRING:
601             hashValue = Hash32(sampleFieldValue.mValue.str_value);
602             break;
603         case STORAGE:
604             hashValue = Hash32((const char*)sampleFieldValue.mValue.storage_value.data(),
605                                sampleFieldValue.mValue.storage_value.size());
606             break;
607         default:
608             return true;
609     }
610     return (hashValue + shardOffset) % shardCount == 0;
611 }
612 
613 }  // namespace statsd
614 }  // namespace os
615 }  // namespace android
616