1 /*
2  * Copyright (C) 2016 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 #ifndef ANDROIDFW_ATTRIBUTE_FINDER_H
18 #define ANDROIDFW_ATTRIBUTE_FINDER_H
19 
20 #include <utils/KeyedVector.h>
21 
22 #include <stdint.h>
23 
24 namespace android {
25 
get_package(uint32_t attr)26 static inline uint32_t get_package(uint32_t attr) { return attr >> 24; }
27 
28 /**
29  * A helper class to search linearly for the requested
30  * attribute, maintaining it's position and optimizing for
31  * the case that subsequent searches will involve an attribute with
32  * a higher attribute ID.
33  *
34  * In the case that a subsequent attribute has a different package ID,
35  * its resource ID may not be larger than the preceding search, so
36  * back tracking is supported for this case. This
37  * back tracking requirement is mainly for shared library
38  * resources, whose package IDs get assigned at runtime
39  * and thus attributes from a shared library may
40  * be out of order.
41  *
42  * We make two assumptions about the order of attributes:
43  * 1) The input has the same sorting rules applied to it as
44  *    the attribute data contained by this class.
45  * 2) Attributes are grouped by package ID.
46  * 3) Among attributes with the same package ID, the attributes are
47  *    sorted by increasing resource ID.
48  *
49  * Ex: 02010000, 02010001, 010100f4, 010100f5, 0x7f010001, 07f010003
50  *
51  * The total order of attributes (including package ID) can not be linear
52  * as shared libraries get assigned dynamic package IDs at runtime, which
53  * may break the sort order established at build time.
54  */
55 template <typename Derived, typename Iterator>
56 class BackTrackingAttributeFinder {
57  public:
58   BackTrackingAttributeFinder(const Iterator& begin, const Iterator& end);
59 
60   Iterator Find(uint32_t attr);
61 
62  private:
63   void JumpToClosestAttribute(uint32_t package_id);
64   void MarkCurrentPackageId(uint32_t package_id);
65 
66   bool first_time_;
67   Iterator begin_;
68   Iterator end_;
69   Iterator current_;
70   Iterator largest_;
71   uint32_t last_package_id_;
72   uint32_t current_attr_;
73 
74   // Package offsets (best-case, fast look-up).
75   Iterator framework_start_;
76   Iterator app_start_;
77 
78   // Worst case, we have shared-library resources.
79   KeyedVector<uint32_t, Iterator> package_offsets_;
80 };
81 
82 template <typename Derived, typename Iterator>
BackTrackingAttributeFinder(const Iterator & begin,const Iterator & end)83 inline BackTrackingAttributeFinder<Derived, Iterator>::BackTrackingAttributeFinder(
84     const Iterator& begin, const Iterator& end)
85     : first_time_(true),
86       begin_(begin),
87       end_(end),
88       current_(begin),
89       largest_(begin),
90       last_package_id_(0),
91       current_attr_(0),
92       framework_start_(end),
93       app_start_(end) {}
94 
95 template <typename Derived, typename Iterator>
JumpToClosestAttribute(const uint32_t package_id)96 void BackTrackingAttributeFinder<Derived, Iterator>::JumpToClosestAttribute(
97     const uint32_t package_id) {
98   switch (package_id) {
99     case 0x01u:
100       current_ = framework_start_;
101       break;
102     case 0x7fu:
103       current_ = app_start_;
104       break;
105     default: {
106       ssize_t idx = package_offsets_.indexOfKey(package_id);
107       if (idx >= 0) {
108         // We have seen this package ID before, so jump to the first
109         // attribute with this package ID.
110         current_ = package_offsets_[idx];
111       } else {
112         current_ = end_;
113       }
114       break;
115     }
116   }
117 
118   // We have never seen this package ID yet, so jump to the
119   // latest/largest index we have processed so far.
120   if (current_ == end_) {
121     current_ = largest_;
122   }
123 
124   if (current_ != end_) {
125     current_attr_ = static_cast<const Derived*>(this)->GetAttribute(current_);
126   }
127 }
128 
129 template <typename Derived, typename Iterator>
MarkCurrentPackageId(const uint32_t package_id)130 void BackTrackingAttributeFinder<Derived, Iterator>::MarkCurrentPackageId(
131     const uint32_t package_id) {
132   switch (package_id) {
133     case 0x01u:
134       framework_start_ = current_;
135       break;
136     case 0x7fu:
137       app_start_ = current_;
138       break;
139     default:
140       package_offsets_.add(package_id, current_);
141       break;
142   }
143 }
144 
145 template <typename Derived, typename Iterator>
Find(uint32_t attr)146 Iterator BackTrackingAttributeFinder<Derived, Iterator>::Find(uint32_t attr) {
147   if (!(begin_ < end_)) {
148     return end_;
149   }
150 
151   if (first_time_) {
152     // One-time initialization. We do this here instead of the constructor
153     // because the derived class we access in getAttribute() may not be
154     // fully constructed.
155     first_time_ = false;
156     current_attr_ = static_cast<const Derived*>(this)->GetAttribute(begin_);
157     last_package_id_ = get_package(current_attr_);
158     MarkCurrentPackageId(last_package_id_);
159   }
160 
161   // Looking for the needle (attribute we're looking for)
162   // in the haystack (the attributes we're searching through)
163   const uint32_t needle_package_id = get_package(attr);
164   if (last_package_id_ != needle_package_id) {
165     JumpToClosestAttribute(needle_package_id);
166     last_package_id_ = needle_package_id;
167   }
168 
169   // Walk through the xml attributes looking for the requested attribute.
170   while (current_ != end_) {
171     const uint32_t haystack_package_id = get_package(current_attr_);
172     if (needle_package_id == haystack_package_id && attr < current_attr_) {
173       // The attribute we are looking was not found.
174       break;
175     }
176     const uint32_t prev_attr = current_attr_;
177 
178     // Move to the next attribute in the XML.
179     ++current_;
180     if (current_ != end_) {
181       current_attr_ = static_cast<const Derived*>(this)->GetAttribute(current_);
182       const uint32_t new_haystack_package_id = get_package(current_attr_);
183       if (haystack_package_id != new_haystack_package_id) {
184         // We've moved to the next group of attributes
185         // with a new package ID, so we should record
186         // the offset of this new package ID.
187         MarkCurrentPackageId(new_haystack_package_id);
188       }
189     }
190 
191     if (current_ > largest_) {
192       // We've moved past the latest attribute we've seen.
193       largest_ = current_;
194     }
195 
196     if (attr == prev_attr) {
197       // We found the attribute we were looking for.
198       return current_ - 1;
199     }
200   }
201   return end_;
202 }
203 
204 }  // namespace android
205 
206 #endif  // ANDROIDFW_ATTRIBUTE_FINDER_H
207