1 /*
2  * Copyright (C) 2017 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 DEBUG false  // STOPSHIP if true
18 #include "Log.h"
19 #include "CombinationConditionTracker.h"
20 
21 namespace android {
22 namespace os {
23 namespace statsd {
24 
25 using std::unordered_map;
26 using std::vector;
27 
28 CombinationConditionTracker::CombinationConditionTracker(const int64_t& id, const int index,
29                                                          const uint64_t protoHash)
30     : ConditionTracker(id, index, protoHash) {
31     VLOG("creating CombinationConditionTracker %lld", (long long)mConditionId);
32 }
33 
34 CombinationConditionTracker::~CombinationConditionTracker() {
35     VLOG("~CombinationConditionTracker() %lld", (long long)mConditionId);
36 }
37 
38 bool CombinationConditionTracker::init(const vector<Predicate>& allConditionConfig,
39                                        const vector<sp<ConditionTracker>>& allConditionTrackers,
40                                        const unordered_map<int64_t, int>& conditionIdIndexMap,
41                                        vector<bool>& stack,
42                                        vector<ConditionState>& conditionCache) {
43     VLOG("Combination predicate init() %lld", (long long)mConditionId);
44     if (mInitialized) {
45         // All the children are guaranteed to be initialized, but the recursion is needed to
46         // fill the conditionCache properly, since another combination condition or metric
47         // might rely on this. The recursion is needed to compute the current condition.
48 
49         // Init is called instead of isConditionMet so that the ConditionKey can be filled with the
50         // default key for sliced conditions, since we do not know all indirect descendants here.
51         for (const int childIndex : mChildren) {
52             if (conditionCache[childIndex] == ConditionState::kNotEvaluated) {
53                 allConditionTrackers[childIndex]->init(allConditionConfig, allConditionTrackers,
54                                                        conditionIdIndexMap, stack, conditionCache);
55             }
56         }
57         conditionCache[mIndex] =
58                 evaluateCombinationCondition(mChildren, mLogicalOperation, conditionCache);
59         return true;
60     }
61 
62     // mark this node as visited in the recursion stack.
63     stack[mIndex] = true;
64 
65     Predicate_Combination combinationCondition = allConditionConfig[mIndex].combination();
66 
67     if (!combinationCondition.has_operation()) {
68         return false;
69     }
70     mLogicalOperation = combinationCondition.operation();
71 
72     if (mLogicalOperation == LogicalOperation::NOT && combinationCondition.predicate_size() != 1) {
73         return false;
74     }
75 
76     for (auto child : combinationCondition.predicate()) {
77         auto it = conditionIdIndexMap.find(child);
78 
79         if (it == conditionIdIndexMap.end()) {
80             ALOGW("Predicate %lld not found in the config", (long long)child);
81             return false;
82         }
83 
84         int childIndex = it->second;
85         const auto& childTracker = allConditionTrackers[childIndex];
86         // if the child is a visited node in the recursion -> circle detected.
87         if (stack[childIndex]) {
88             ALOGW("Circle detected!!!");
89             return false;
90         }
91 
92         bool initChildSucceeded = childTracker->init(allConditionConfig, allConditionTrackers,
93                                                      conditionIdIndexMap, stack, conditionCache);
94 
95         if (!initChildSucceeded) {
96             ALOGW("Child initialization failed %lld ", (long long)child);
97             return false;
98         } else {
99             VLOG("Child initialization success %lld ", (long long)child);
100         }
101 
102         if (allConditionTrackers[childIndex]->isSliced()) {
103             setSliced(true);
104             mSlicedChildren.push_back(childIndex);
105         } else {
106             mUnSlicedChildren.push_back(childIndex);
107         }
108         mChildren.push_back(childIndex);
109         mTrackerIndex.insert(childTracker->getAtomMatchingTrackerIndex().begin(),
110                              childTracker->getAtomMatchingTrackerIndex().end());
111     }
112 
113     mUnSlicedPartCondition =
114             evaluateCombinationCondition(mUnSlicedChildren, mLogicalOperation, conditionCache);
115     conditionCache[mIndex] =
116             evaluateCombinationCondition(mChildren, mLogicalOperation, conditionCache);
117 
118     // unmark this node in the recursion stack.
119     stack[mIndex] = false;
120 
121     mInitialized = true;
122 
123     return true;
124 }
125 
126 bool CombinationConditionTracker::onConfigUpdated(
127         const vector<Predicate>& allConditionProtos, const int index,
128         const vector<sp<ConditionTracker>>& allConditionTrackers,
129         const unordered_map<int64_t, int>& atomMatchingTrackerMap,
130         const unordered_map<int64_t, int>& conditionTrackerMap) {
131     ConditionTracker::onConfigUpdated(allConditionProtos, index, allConditionTrackers,
132                                       atomMatchingTrackerMap, conditionTrackerMap);
133     mTrackerIndex.clear();
134     mChildren.clear();
135     mUnSlicedChildren.clear();
136     mSlicedChildren.clear();
137     Predicate_Combination combinationCondition = allConditionProtos[mIndex].combination();
138 
139     for (const int64_t child : combinationCondition.predicate()) {
140         const auto& it = conditionTrackerMap.find(child);
141 
142         if (it == conditionTrackerMap.end()) {
143             ALOGW("Predicate %lld not found in the config", (long long)child);
144             return false;
145         }
146 
147         int childIndex = it->second;
148         const sp<ConditionTracker>& childTracker = allConditionTrackers[childIndex];
149 
150         // Ensures that the child's tracker indices are updated.
151         if (!childTracker->onConfigUpdated(allConditionProtos, childIndex, allConditionTrackers,
152                                            atomMatchingTrackerMap, conditionTrackerMap)) {
153             ALOGW("Child update failed %lld ", (long long)child);
154             return false;
155         }
156 
157         if (allConditionTrackers[childIndex]->isSliced()) {
158             mSlicedChildren.push_back(childIndex);
159         } else {
160             mUnSlicedChildren.push_back(childIndex);
161         }
162         mChildren.push_back(childIndex);
163         mTrackerIndex.insert(childTracker->getAtomMatchingTrackerIndex().begin(),
164                              childTracker->getAtomMatchingTrackerIndex().end());
165     }
166     return true;
167 }
168 
169 void CombinationConditionTracker::isConditionMet(
170         const ConditionKey& conditionParameters, const vector<sp<ConditionTracker>>& allConditions,
171         const bool isPartialLink,
172         vector<ConditionState>& conditionCache) const {
173     // So far, this is fine as there is at most one child having sliced output.
174     for (const int childIndex : mChildren) {
175         if (conditionCache[childIndex] == ConditionState::kNotEvaluated) {
176             allConditions[childIndex]->isConditionMet(conditionParameters, allConditions,
177                                                       isPartialLink,
178                                                       conditionCache);
179         }
180     }
181     conditionCache[mIndex] =
182             evaluateCombinationCondition(mChildren, mLogicalOperation, conditionCache);
183 }
184 
185 void CombinationConditionTracker::evaluateCondition(
186         const LogEvent& event, const std::vector<MatchingState>& eventMatcherValues,
187         const std::vector<sp<ConditionTracker>>& mAllConditions,
188         std::vector<ConditionState>& nonSlicedConditionCache,
189         std::vector<bool>& conditionChangedCache) {
190     // value is up to date.
191     if (nonSlicedConditionCache[mIndex] != ConditionState::kNotEvaluated) {
192         return;
193     }
194 
195     for (const int childIndex : mChildren) {
196         // So far, this is fine as there is at most one child having sliced output.
197         if (nonSlicedConditionCache[childIndex] == ConditionState::kNotEvaluated) {
198             const sp<ConditionTracker>& child = mAllConditions[childIndex];
199             child->evaluateCondition(event, eventMatcherValues, mAllConditions,
200                                      nonSlicedConditionCache, conditionChangedCache);
201         }
202     }
203 
204     ConditionState newCondition =
205             evaluateCombinationCondition(mChildren, mLogicalOperation, nonSlicedConditionCache);
206     if (!mSliced) {
207         bool nonSlicedChanged = (mUnSlicedPartCondition != newCondition);
208         mUnSlicedPartCondition = newCondition;
209 
210         nonSlicedConditionCache[mIndex] = mUnSlicedPartCondition;
211         conditionChangedCache[mIndex] = nonSlicedChanged;
212     } else {
213         mUnSlicedPartCondition = evaluateCombinationCondition(mUnSlicedChildren, mLogicalOperation,
214                                                               nonSlicedConditionCache);
215 
216         for (const int childIndex : mChildren) {
217             // If any of the sliced condition in children condition changes, the combination
218             // condition may be changed too.
219             if (conditionChangedCache[childIndex]) {
220                 conditionChangedCache[mIndex] = true;
221                 break;
222             }
223         }
224         nonSlicedConditionCache[mIndex] = newCondition;
225         VLOG("CombinationPredicate %lld sliced may changed? %d", (long long)mConditionId,
226             conditionChangedCache[mIndex] == true);
227     }
228 }
229 
230 bool CombinationConditionTracker::equalOutputDimensions(
231         const std::vector<sp<ConditionTracker>>& allConditions,
232         const vector<Matcher>& dimensions) const {
233     if (mSlicedChildren.size() != 1 ||
234         mSlicedChildren.front() >= (int)allConditions.size() ||
235         mLogicalOperation != LogicalOperation::AND) {
236         return false;
237     }
238     const sp<ConditionTracker>& slicedChild = allConditions.at(mSlicedChildren.front());
239     return slicedChild->equalOutputDimensions(allConditions, dimensions);
240 }
241 
242 }  // namespace statsd
243 }  // namespace os
244 }  // namespace android
245