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 #include "SensorsHidlEnvironmentV2_X.h"
17 #include "convertV2_1.h"
18 #include "sensors-vts-utils/SensorsHidlTestBase.h"
19 #include "sensors-vts-utils/SensorsTestSharedMemory.h"
20 
21 #include <android/hardware/sensors/2.1/ISensors.h>
22 #include <android/hardware/sensors/2.1/types.h>
23 
24 #include <hidl/GtestPrinter.h>
25 #include <hidl/ServiceManagement.h>
26 #include <log/log.h>
27 #include <utils/SystemClock.h>
28 
29 #include <algorithm>
30 #include <cinttypes>
31 #include <condition_variable>
32 #include <cstring>
33 #include <map>
34 #include <unordered_map>
35 #include <vector>
36 
37 /**
38  * This file contains the core tests and test logic for both sensors HAL 2.0
39  * and 2.1. To make it easier to share the code between both VTS test suites,
40  * this is defined as a header so they can both include and use all pieces of
41  * code.
42  */
43 
44 using ::android::sp;
45 using ::android::hardware::Return;
46 using ::android::hardware::Void;
47 using ::android::hardware::sensors::V1_0::MetaDataEventType;
48 using ::android::hardware::sensors::V1_0::OperationMode;
49 using ::android::hardware::sensors::V1_0::SensorsEventFormatOffset;
50 using ::android::hardware::sensors::V1_0::SensorStatus;
51 using ::android::hardware::sensors::V1_0::SharedMemType;
52 using ::android::hardware::sensors::V1_0::Vec3;
53 using ::android::hardware::sensors::V2_1::implementation::convertToOldSensorInfos;
54 using std::chrono::duration_cast;
55 using std::chrono::nanoseconds;
56 
57 using EventV1_0 = ::android::hardware::sensors::V1_0::Event;
58 using ISensorsType = ::android::hardware::sensors::V2_1::ISensors;
59 using SensorTypeVersion = ::android::hardware::sensors::V2_1::SensorType;
60 using EventType = ::android::hardware::sensors::V2_1::Event;
61 using SensorInfoType = ::android::hardware::sensors::V2_1::SensorInfo;
62 using SensorsHidlTestBaseV2_X = SensorsHidlTestBase<SensorTypeVersion, EventType, SensorInfoType>;
63 
64 constexpr size_t kEventSize = static_cast<size_t>(SensorsEventFormatOffset::TOTAL_LENGTH);
65 
66 class EventCallback : public IEventCallback<EventType> {
67   public:
reset()68     void reset() {
69         mFlushMap.clear();
70         mEventMap.clear();
71     }
72 
onEvent(const EventType & event)73     void onEvent(const EventType& event) override {
74         if (event.sensorType == SensorTypeVersion::META_DATA &&
75             event.u.meta.what == MetaDataEventType::META_DATA_FLUSH_COMPLETE) {
76             std::unique_lock<std::recursive_mutex> lock(mFlushMutex);
77             mFlushMap[event.sensorHandle]++;
78             mFlushCV.notify_all();
79         } else if (event.sensorType != SensorTypeVersion::ADDITIONAL_INFO) {
80             std::unique_lock<std::recursive_mutex> lock(mEventMutex);
81             mEventMap[event.sensorHandle].push_back(event);
82             mEventCV.notify_all();
83         }
84     }
85 
getFlushCount(int32_t sensorHandle)86     int32_t getFlushCount(int32_t sensorHandle) {
87         std::unique_lock<std::recursive_mutex> lock(mFlushMutex);
88         return mFlushMap[sensorHandle];
89     }
90 
waitForFlushEvents(const std::vector<SensorInfoType> & sensorsToWaitFor,int32_t numCallsToFlush,std::chrono::milliseconds timeout)91     void waitForFlushEvents(const std::vector<SensorInfoType>& sensorsToWaitFor,
92                             int32_t numCallsToFlush, std::chrono::milliseconds timeout) {
93         std::unique_lock<std::recursive_mutex> lock(mFlushMutex);
94         mFlushCV.wait_for(lock, timeout,
95                           [&] { return flushesReceived(sensorsToWaitFor, numCallsToFlush); });
96     }
97 
getEvents(int32_t sensorHandle)98     const std::vector<EventType> getEvents(int32_t sensorHandle) {
99         std::unique_lock<std::recursive_mutex> lock(mEventMutex);
100         return mEventMap[sensorHandle];
101     }
102 
waitForEvents(const std::vector<SensorInfoType> & sensorsToWaitFor,std::chrono::milliseconds timeout)103     void waitForEvents(const std::vector<SensorInfoType>& sensorsToWaitFor,
104                        std::chrono::milliseconds timeout) {
105         std::unique_lock<std::recursive_mutex> lock(mEventMutex);
106         mEventCV.wait_for(lock, timeout, [&] { return eventsReceived(sensorsToWaitFor); });
107     }
108 
109   protected:
flushesReceived(const std::vector<SensorInfoType> & sensorsToWaitFor,int32_t numCallsToFlush)110     bool flushesReceived(const std::vector<SensorInfoType>& sensorsToWaitFor,
111                          int32_t numCallsToFlush) {
112         for (const SensorInfoType& sensor : sensorsToWaitFor) {
113             if (getFlushCount(sensor.sensorHandle) < numCallsToFlush) {
114                 return false;
115             }
116         }
117         return true;
118     }
119 
eventsReceived(const std::vector<SensorInfoType> & sensorsToWaitFor)120     bool eventsReceived(const std::vector<SensorInfoType>& sensorsToWaitFor) {
121         for (const SensorInfoType& sensor : sensorsToWaitFor) {
122             if (getEvents(sensor.sensorHandle).size() == 0) {
123                 return false;
124             }
125         }
126         return true;
127     }
128 
129     std::map<int32_t, int32_t> mFlushMap;
130     std::recursive_mutex mFlushMutex;
131     std::condition_variable_any mFlushCV;
132 
133     std::map<int32_t, std::vector<EventType>> mEventMap;
134     std::recursive_mutex mEventMutex;
135     std::condition_variable_any mEventCV;
136 };
137 
138 /**
139  * Define the template specific versions of the static helper methods in
140  * SensorsHidlTestBase used to test that hinge angle is exposed properly.
141  */
142 template <>
expectedReportModeForType(::android::hardware::sensors::V2_1::SensorType type)143 SensorFlagBits expectedReportModeForType(::android::hardware::sensors::V2_1::SensorType type) {
144     switch (type) {
145         case ::android::hardware::sensors::V2_1::SensorType::HINGE_ANGLE:
146             return SensorFlagBits::ON_CHANGE_MODE;
147         default:
148             return expectedReportModeForType(
149                     static_cast<::android::hardware::sensors::V1_0::SensorType>(type));
150     }
151 }
152 
153 template <>
assertTypeMatchStringType(::android::hardware::sensors::V2_1::SensorType type,const hidl_string & stringType)154 void assertTypeMatchStringType(::android::hardware::sensors::V2_1::SensorType type,
155                                const hidl_string& stringType) {
156     switch (type) {
157         case (::android::hardware::sensors::V2_1::SensorType::HINGE_ANGLE):
158             ASSERT_STREQ(SENSOR_STRING_TYPE_HINGE_ANGLE, stringType.c_str());
159             break;
160         default:
161             assertTypeMatchStringType(
162                     static_cast<::android::hardware::sensors::V1_0::SensorType>(type), stringType);
163             break;
164     }
165 }
166 
167 // The main test class for SENSORS HIDL HAL.
168 class SensorsHidlTest : public SensorsHidlTestBaseV2_X {
169   public:
SetUp()170     virtual void SetUp() override {
171         mEnvironment = new SensorsHidlEnvironmentV2_X(GetParam());
172         mEnvironment->SetUp();
173         // Ensure that we have a valid environment before performing tests
174         ASSERT_NE(getSensors(), nullptr);
175     }
176 
TearDown()177     virtual void TearDown() override { mEnvironment->TearDown(); }
178 
179   protected:
180     SensorInfoType defaultSensorByType(SensorTypeVersion type) override;
181     std::vector<SensorInfoType> getSensorsList();
182     // implementation wrapper
183 
getSensorsList(ISensorsType::getSensorsList_cb _hidl_cb)184     Return<void> getSensorsList(ISensorsType::getSensorsList_cb _hidl_cb) override {
185         return getSensors()->getSensorsList(
186                 [&](const auto& list) { _hidl_cb(convertToOldSensorInfos(list)); });
187     }
188 
189     Return<Result> activate(int32_t sensorHandle, bool enabled) override;
190 
batch(int32_t sensorHandle,int64_t samplingPeriodNs,int64_t maxReportLatencyNs)191     Return<Result> batch(int32_t sensorHandle, int64_t samplingPeriodNs,
192                          int64_t maxReportLatencyNs) override {
193         return getSensors()->batch(sensorHandle, samplingPeriodNs, maxReportLatencyNs);
194     }
195 
flush(int32_t sensorHandle)196     Return<Result> flush(int32_t sensorHandle) override {
197         return getSensors()->flush(sensorHandle);
198     }
199 
injectSensorData(const EventType & event)200     Return<Result> injectSensorData(const EventType& event) override {
201         return getSensors()->injectSensorData(event);
202     }
203 
204     Return<void> registerDirectChannel(const SharedMemInfo& mem,
205                                        ISensorsType::registerDirectChannel_cb _hidl_cb) override;
206 
unregisterDirectChannel(int32_t channelHandle)207     Return<Result> unregisterDirectChannel(int32_t channelHandle) override {
208         return getSensors()->unregisterDirectChannel(channelHandle);
209     }
210 
configDirectReport(int32_t sensorHandle,int32_t channelHandle,RateLevel rate,ISensorsType::configDirectReport_cb _hidl_cb)211     Return<void> configDirectReport(int32_t sensorHandle, int32_t channelHandle, RateLevel rate,
212                                     ISensorsType::configDirectReport_cb _hidl_cb) override {
213         return getSensors()->configDirectReport(sensorHandle, channelHandle, rate, _hidl_cb);
214     }
215 
getSensors()216     inline sp<ISensorsWrapperBase>& getSensors() { return mEnvironment->mSensors; }
217 
getEnvironment()218     SensorsVtsEnvironmentBase<EventType>* getEnvironment() override { return mEnvironment; }
219 
220     // Test helpers
221     void runSingleFlushTest(const std::vector<SensorInfoType>& sensors, bool activateSensor,
222                             int32_t expectedFlushCount, Result expectedResponse);
223     void runFlushTest(const std::vector<SensorInfoType>& sensors, bool activateSensor,
224                       int32_t flushCalls, int32_t expectedFlushCount, Result expectedResponse);
225 
226     // Helper functions
227     void activateAllSensors(bool enable);
228     std::vector<SensorInfoType> getNonOneShotSensors();
229     std::vector<SensorInfoType> getNonOneShotAndNonSpecialSensors();
230     std::vector<SensorInfoType> getNonOneShotAndNonOnChangeAndNonSpecialSensors();
231     std::vector<SensorInfoType> getOneShotSensors();
232     std::vector<SensorInfoType> getInjectEventSensors();
233     int32_t getInvalidSensorHandle();
234     bool getDirectChannelSensor(SensorInfoType* sensor, SharedMemType* memType, RateLevel* rate);
235     void verifyDirectChannel(SharedMemType memType);
236     void verifyRegisterDirectChannel(
237             std::shared_ptr<SensorsTestSharedMemory<SensorTypeVersion, EventType>> mem,
238             int32_t* directChannelHandle, bool supportsSharedMemType,
239             bool supportsAnyDirectChannel);
240     void verifyConfigure(const SensorInfoType& sensor, SharedMemType memType,
241                          int32_t directChannelHandle, bool directChannelSupported);
242     void verifyUnregisterDirectChannel(int32_t directChannelHandle, bool directChannelSupported);
243     void checkRateLevel(const SensorInfoType& sensor, int32_t directChannelHandle,
244                         RateLevel rateLevel);
245     void queryDirectChannelSupport(SharedMemType memType, bool* supportsSharedMemType,
246                                    bool* supportsAnyDirectChannel);
247 
248   private:
249     // Test environment for sensors HAL.
250     SensorsHidlEnvironmentV2_X* mEnvironment;
251 };
252 
activate(int32_t sensorHandle,bool enabled)253 Return<Result> SensorsHidlTest::activate(int32_t sensorHandle, bool enabled) {
254     // If activating a sensor, add the handle in a set so that when test fails it can be turned off.
255     // The handle is not removed when it is deactivating on purpose so that it is not necessary to
256     // check the return value of deactivation. Deactivating a sensor more than once does not have
257     // negative effect.
258     if (enabled) {
259         mSensorHandles.insert(sensorHandle);
260     }
261     return getSensors()->activate(sensorHandle, enabled);
262 }
263 
registerDirectChannel(const SharedMemInfo & mem,ISensors::registerDirectChannel_cb cb)264 Return<void> SensorsHidlTest::registerDirectChannel(const SharedMemInfo& mem,
265                                                     ISensors::registerDirectChannel_cb cb) {
266     // If registeration of a channel succeeds, add the handle of channel to a set so that it can be
267     // unregistered when test fails. Unregister a channel does not remove the handle on purpose.
268     // Unregistering a channel more than once should not have negative effect.
269     getSensors()->registerDirectChannel(mem, [&](auto result, auto channelHandle) {
270         if (result == Result::OK) {
271             mDirectChannelHandles.insert(channelHandle);
272         }
273         cb(result, channelHandle);
274     });
275     return Void();
276 }
277 
defaultSensorByType(SensorTypeVersion type)278 SensorInfoType SensorsHidlTest::defaultSensorByType(SensorTypeVersion type) {
279     SensorInfoType ret;
280 
281     ret.type = (SensorTypeVersion)-1;
282     getSensors()->getSensorsList([&](const auto& list) {
283         const size_t count = list.size();
284         for (size_t i = 0; i < count; ++i) {
285             if (list[i].type == type) {
286                 ret = list[i];
287                 return;
288             }
289         }
290     });
291 
292     return ret;
293 }
294 
getSensorsList()295 std::vector<SensorInfoType> SensorsHidlTest::getSensorsList() {
296     std::vector<SensorInfoType> ret;
297 
298     getSensors()->getSensorsList([&](const auto& list) {
299         const size_t count = list.size();
300         ret.reserve(list.size());
301         for (size_t i = 0; i < count; ++i) {
302             ret.push_back(list[i]);
303         }
304     });
305 
306     return ret;
307 }
308 
getNonOneShotSensors()309 std::vector<SensorInfoType> SensorsHidlTest::getNonOneShotSensors() {
310     std::vector<SensorInfoType> sensors;
311     for (const SensorInfoType& info : getSensorsList()) {
312         if (extractReportMode(info.flags) != SensorFlagBits::ONE_SHOT_MODE) {
313             sensors.push_back(info);
314         }
315     }
316     return sensors;
317 }
318 
getNonOneShotAndNonSpecialSensors()319 std::vector<SensorInfoType> SensorsHidlTest::getNonOneShotAndNonSpecialSensors() {
320     std::vector<SensorInfoType> sensors;
321     for (const SensorInfoType& info : getSensorsList()) {
322         SensorFlagBits reportMode = extractReportMode(info.flags);
323         if (reportMode != SensorFlagBits::ONE_SHOT_MODE &&
324             reportMode != SensorFlagBits::SPECIAL_REPORTING_MODE) {
325             sensors.push_back(info);
326         }
327     }
328     return sensors;
329 }
330 
getNonOneShotAndNonOnChangeAndNonSpecialSensors()331 std::vector<SensorInfoType> SensorsHidlTest::getNonOneShotAndNonOnChangeAndNonSpecialSensors() {
332     std::vector<SensorInfoType> sensors;
333     for (const SensorInfoType& info : getSensorsList()) {
334         SensorFlagBits reportMode = extractReportMode(info.flags);
335         if (reportMode != SensorFlagBits::ONE_SHOT_MODE &&
336             reportMode != SensorFlagBits::ON_CHANGE_MODE &&
337             reportMode != SensorFlagBits::SPECIAL_REPORTING_MODE) {
338             sensors.push_back(info);
339         }
340     }
341     return sensors;
342 }
343 
getOneShotSensors()344 std::vector<SensorInfoType> SensorsHidlTest::getOneShotSensors() {
345     std::vector<SensorInfoType> sensors;
346     for (const SensorInfoType& info : getSensorsList()) {
347         if (extractReportMode(info.flags) == SensorFlagBits::ONE_SHOT_MODE) {
348             sensors.push_back(info);
349         }
350     }
351     return sensors;
352 }
353 
getInjectEventSensors()354 std::vector<SensorInfoType> SensorsHidlTest::getInjectEventSensors() {
355     std::vector<SensorInfoType> sensors;
356     for (const SensorInfoType& info : getSensorsList()) {
357         if (info.flags & static_cast<uint32_t>(SensorFlagBits::DATA_INJECTION)) {
358             sensors.push_back(info);
359         }
360     }
361     return sensors;
362 }
363 
getInvalidSensorHandle()364 int32_t SensorsHidlTest::getInvalidSensorHandle() {
365     // Find a sensor handle that does not exist in the sensor list
366     int32_t maxHandle = 0;
367     for (const SensorInfoType& sensor : getSensorsList()) {
368         maxHandle = std::max(maxHandle, sensor.sensorHandle);
369     }
370     return maxHandle + 42;
371 }
372 
373 // Test if sensor list returned is valid
TEST_P(SensorsHidlTest,SensorListValid)374 TEST_P(SensorsHidlTest, SensorListValid) {
375     getSensors()->getSensorsList([&](const auto& list) {
376         const size_t count = list.size();
377         std::unordered_map<int32_t, std::vector<std::string>> sensorTypeNameMap;
378         for (size_t i = 0; i < count; ++i) {
379             const auto& s = list[i];
380             SCOPED_TRACE(::testing::Message()
381                          << i << "/" << count << ": "
382                          << " handle=0x" << std::hex << std::setw(8) << std::setfill('0')
383                          << s.sensorHandle << std::dec << " type=" << static_cast<int>(s.type)
384                          << " name=" << s.name);
385 
386             // Test type string non-empty only for private sensor types.
387             if (s.type >= SensorTypeVersion::DEVICE_PRIVATE_BASE) {
388                 EXPECT_FALSE(s.typeAsString.empty());
389             } else if (!s.typeAsString.empty()) {
390                 // Test type string matches framework string if specified for non-private types.
391                 EXPECT_NO_FATAL_FAILURE(assertTypeMatchStringType(s.type, s.typeAsString));
392             }
393 
394             // Test if all sensor has name and vendor
395             EXPECT_FALSE(s.name.empty());
396             EXPECT_FALSE(s.vendor.empty());
397 
398             // Make sure that sensors of the same type have a unique name.
399             std::vector<std::string>& v = sensorTypeNameMap[static_cast<int32_t>(s.type)];
400             bool isUniqueName = std::find(v.begin(), v.end(), s.name) == v.end();
401             EXPECT_TRUE(isUniqueName) << "Duplicate sensor Name: " << s.name;
402             if (isUniqueName) {
403                 v.push_back(s.name);
404             }
405 
406             // Test power > 0, maxRange > 0
407             EXPECT_LE(0, s.power);
408             EXPECT_LT(0, s.maxRange);
409 
410             // Info type, should have no sensor
411             EXPECT_FALSE(s.type == SensorTypeVersion::ADDITIONAL_INFO ||
412                          s.type == SensorTypeVersion::META_DATA);
413 
414             // Test fifoMax >= fifoReserved
415             EXPECT_GE(s.fifoMaxEventCount, s.fifoReservedEventCount)
416                     << "max=" << s.fifoMaxEventCount << " reserved=" << s.fifoReservedEventCount;
417 
418             // Test Reporting mode valid
419             EXPECT_NO_FATAL_FAILURE(assertTypeMatchReportMode(s.type, extractReportMode(s.flags)));
420 
421             // Test min max are in the right order
422             EXPECT_LE(s.minDelay, s.maxDelay);
423             // Test min/max delay matches reporting mode
424             EXPECT_NO_FATAL_FAILURE(
425                     assertDelayMatchReportMode(s.minDelay, s.maxDelay, extractReportMode(s.flags)));
426         }
427     });
428 }
429 
430 // Test that SetOperationMode returns the expected value
TEST_P(SensorsHidlTest,SetOperationMode)431 TEST_P(SensorsHidlTest, SetOperationMode) {
432     std::vector<SensorInfoType> sensors = getInjectEventSensors();
433     if (getInjectEventSensors().size() > 0) {
434         ASSERT_EQ(Result::OK, getSensors()->setOperationMode(OperationMode::NORMAL));
435         ASSERT_EQ(Result::OK, getSensors()->setOperationMode(OperationMode::DATA_INJECTION));
436         ASSERT_EQ(Result::OK, getSensors()->setOperationMode(OperationMode::NORMAL));
437     } else {
438         ASSERT_EQ(Result::BAD_VALUE, getSensors()->setOperationMode(OperationMode::DATA_INJECTION));
439     }
440 }
441 
442 // Test that an injected event is written back to the Event FMQ
TEST_P(SensorsHidlTest,InjectSensorEventData)443 TEST_P(SensorsHidlTest, InjectSensorEventData) {
444     std::vector<SensorInfoType> sensors = getInjectEventSensors();
445     if (sensors.size() == 0) {
446         return;
447     }
448 
449     ASSERT_EQ(Result::OK, getSensors()->setOperationMode(OperationMode::DATA_INJECTION));
450 
451     EventCallback callback;
452     getEnvironment()->registerCallback(&callback);
453 
454     // AdditionalInfo event should not be sent to Event FMQ
455     EventType additionalInfoEvent;
456     additionalInfoEvent.sensorType = SensorTypeVersion::ADDITIONAL_INFO;
457     additionalInfoEvent.timestamp = android::elapsedRealtimeNano();
458 
459     EventType injectedEvent;
460     injectedEvent.timestamp = android::elapsedRealtimeNano();
461     Vec3 data = {1, 2, 3, SensorStatus::ACCURACY_HIGH};
462     injectedEvent.u.vec3 = data;
463 
464     for (const auto& s : sensors) {
465         additionalInfoEvent.sensorHandle = s.sensorHandle;
466         EXPECT_EQ(Result::OK, getSensors()->injectSensorData(additionalInfoEvent));
467 
468         injectedEvent.sensorType = s.type;
469         injectedEvent.sensorHandle = s.sensorHandle;
470         EXPECT_EQ(Result::OK, getSensors()->injectSensorData(injectedEvent));
471     }
472 
473     // Wait for events to be written back to the Event FMQ
474     callback.waitForEvents(sensors, std::chrono::milliseconds(1000) /* timeout */);
475     getEnvironment()->unregisterCallback();
476 
477     for (const auto& s : sensors) {
478         auto events = callback.getEvents(s.sensorHandle);
479         auto lastEvent = events.back();
480         SCOPED_TRACE(::testing::Message()
481                      << " handle=0x" << std::hex << std::setw(8) << std::setfill('0')
482                      << s.sensorHandle << std::dec << " type=" << static_cast<int>(s.type)
483                      << " name=" << s.name);
484 
485         // Verify that only a single event has been received
486         ASSERT_EQ(events.size(), 1);
487 
488         // Verify that the event received matches the event injected and is not the additional
489         // info event
490         ASSERT_EQ(lastEvent.sensorType, s.type);
491         ASSERT_EQ(lastEvent.sensorType, s.type);
492         ASSERT_EQ(lastEvent.timestamp, injectedEvent.timestamp);
493         ASSERT_EQ(lastEvent.u.vec3.x, injectedEvent.u.vec3.x);
494         ASSERT_EQ(lastEvent.u.vec3.y, injectedEvent.u.vec3.y);
495         ASSERT_EQ(lastEvent.u.vec3.z, injectedEvent.u.vec3.z);
496         ASSERT_EQ(lastEvent.u.vec3.status, injectedEvent.u.vec3.status);
497     }
498 
499     ASSERT_EQ(Result::OK, getSensors()->setOperationMode(OperationMode::NORMAL));
500 }
501 
activateAllSensors(bool enable)502 void SensorsHidlTest::activateAllSensors(bool enable) {
503     for (const SensorInfoType& sensorInfo : getSensorsList()) {
504         if (isValidType(sensorInfo.type)) {
505             batch(sensorInfo.sensorHandle, sensorInfo.minDelay, 0 /* maxReportLatencyNs */);
506             activate(sensorInfo.sensorHandle, enable);
507         }
508     }
509 }
510 
511 // Test that if initialize is called twice, then the HAL writes events to the FMQs from the second
512 // call to the function.
TEST_P(SensorsHidlTest,CallInitializeTwice)513 TEST_P(SensorsHidlTest, CallInitializeTwice) {
514     // Create a helper class so that a second environment is able to be instantiated
515     class SensorsHidlEnvironmentTest : public SensorsHidlEnvironmentV2_X {
516       public:
517         SensorsHidlEnvironmentTest(const std::string& service_name)
518             : SensorsHidlEnvironmentV2_X(service_name) {}
519     };
520 
521     if (getSensorsList().size() == 0) {
522         // No sensors
523         return;
524     }
525 
526     constexpr useconds_t kCollectionTimeoutUs = 1000 * 1000;  // 1s
527     constexpr int32_t kNumEvents = 1;
528 
529     // Create a new environment that calls initialize()
530     std::unique_ptr<SensorsHidlEnvironmentTest> newEnv =
531             std::make_unique<SensorsHidlEnvironmentTest>(GetParam());
532     newEnv->SetUp();
533     if (HasFatalFailure()) {
534         return;  // Exit early if setting up the new environment failed
535     }
536 
537     activateAllSensors(true);
538     // Verify that the old environment does not receive any events
539     EXPECT_EQ(getEnvironment()->collectEvents(kCollectionTimeoutUs, kNumEvents).size(), 0);
540     // Verify that the new event queue receives sensor events
541     EXPECT_GE(newEnv.get()->collectEvents(kCollectionTimeoutUs, kNumEvents).size(), kNumEvents);
542     activateAllSensors(false);
543 
544     // Cleanup the test environment
545     newEnv->TearDown();
546 
547     // Restore the test environment for future tests
548     getEnvironment()->TearDown();
549     getEnvironment()->SetUp();
550     if (HasFatalFailure()) {
551         return;  // Exit early if resetting the environment failed
552     }
553 
554     // Ensure that the original environment is receiving events
555     activateAllSensors(true);
556     EXPECT_GE(getEnvironment()->collectEvents(kCollectionTimeoutUs, kNumEvents).size(), kNumEvents);
557     activateAllSensors(false);
558 }
559 
TEST_P(SensorsHidlTest,CleanupConnectionsOnInitialize)560 TEST_P(SensorsHidlTest, CleanupConnectionsOnInitialize) {
561     if (getSensorsList().size() == 0) {
562         // No sensors
563         return;
564     }
565 
566     activateAllSensors(true);
567 
568     // Verify that events are received
569     constexpr useconds_t kCollectionTimeoutUs = 1000 * 1000;  // 1s
570     constexpr int32_t kNumEvents = 1;
571     ASSERT_GE(getEnvironment()->collectEvents(kCollectionTimeoutUs, kNumEvents).size(), kNumEvents);
572 
573     // Clear the active sensor handles so they are not disabled during TearDown
574     auto handles = mSensorHandles;
575     mSensorHandles.clear();
576     getEnvironment()->TearDown();
577     getEnvironment()->SetUp();
578     if (HasFatalFailure()) {
579         return;  // Exit early if resetting the environment failed
580     }
581 
582     // Verify no events are received until sensors are re-activated
583     ASSERT_EQ(getEnvironment()->collectEvents(kCollectionTimeoutUs, kNumEvents).size(), 0);
584     activateAllSensors(true);
585     ASSERT_GE(getEnvironment()->collectEvents(kCollectionTimeoutUs, kNumEvents).size(), kNumEvents);
586 
587     // Disable sensors
588     activateAllSensors(false);
589 
590     // Restore active sensors prior to clearing the environment
591     mSensorHandles = handles;
592 }
593 
runSingleFlushTest(const std::vector<SensorInfoType> & sensors,bool activateSensor,int32_t expectedFlushCount,Result expectedResponse)594 void SensorsHidlTest::runSingleFlushTest(const std::vector<SensorInfoType>& sensors,
595                                          bool activateSensor, int32_t expectedFlushCount,
596                                          Result expectedResponse) {
597     runFlushTest(sensors, activateSensor, 1 /* flushCalls */, expectedFlushCount, expectedResponse);
598 }
599 
runFlushTest(const std::vector<SensorInfoType> & sensors,bool activateSensor,int32_t flushCalls,int32_t expectedFlushCount,Result expectedResponse)600 void SensorsHidlTest::runFlushTest(const std::vector<SensorInfoType>& sensors, bool activateSensor,
601                                    int32_t flushCalls, int32_t expectedFlushCount,
602                                    Result expectedResponse) {
603     EventCallback callback;
604     getEnvironment()->registerCallback(&callback);
605 
606     // 10 sensors per group
607     constexpr size_t kSensorsPerGroup = 10;
608     for (size_t sensorOffset = 0; sensorOffset < sensors.size();
609          sensorOffset += kSensorsPerGroup) {
610         std::vector<SensorInfoType> sensorGroup(
611             sensors.begin() + sensorOffset,
612             sensors.begin() +
613                 std::min(sensorOffset + kSensorsPerGroup, sensors.size()));
614 
615         for (const SensorInfoType& sensor : sensorGroup) {
616             // Configure and activate the sensor
617             batch(sensor.sensorHandle, sensor.maxDelay, 0 /* maxReportLatencyNs */);
618             activate(sensor.sensorHandle, activateSensor);
619 
620             // Flush the sensor
621             for (int32_t i = 0; i < flushCalls; i++) {
622                 SCOPED_TRACE(::testing::Message()
623                              << "Flush " << i << "/" << flushCalls << ": "
624                              << " handle=0x" << std::hex << std::setw(8) << std::setfill('0')
625                              << sensor.sensorHandle << std::dec
626                              << " type=" << static_cast<int>(sensor.type)
627                              << " name=" << sensor.name);
628 
629                 Result flushResult = flush(sensor.sensorHandle);
630                 EXPECT_EQ(flushResult, expectedResponse);
631             }
632         }
633 
634         // Wait up to one second for the flush events
635         callback.waitForFlushEvents(sensorGroup, flushCalls,
636                                     std::chrono::milliseconds(1000) /* timeout */);
637 
638         // Deactivate all sensors after waiting for flush events so pending flush events are not
639         // abandoned by the HAL.
640         for (const SensorInfoType& sensor : sensorGroup) {
641             activate(sensor.sensorHandle, false);
642         }
643 
644         // Check that the correct number of flushes are present for each sensor
645         for (const SensorInfoType& sensor : sensorGroup) {
646             SCOPED_TRACE(::testing::Message()
647                          << " handle=0x" << std::hex << std::setw(8) << std::setfill('0')
648                          << sensor.sensorHandle << std::dec
649                          << " type=" << static_cast<int>(sensor.type)
650                          << " name=" << sensor.name);
651             ASSERT_EQ(callback.getFlushCount(sensor.sensorHandle), expectedFlushCount);
652         }
653     }
654     getEnvironment()->unregisterCallback();
655 }
656 
TEST_P(SensorsHidlTest,FlushSensor)657 TEST_P(SensorsHidlTest, FlushSensor) {
658     // Find a sensor that is not a one-shot sensor
659     std::vector<SensorInfoType> sensors = getNonOneShotSensors();
660     if (sensors.size() == 0) {
661         return;
662     }
663 
664     constexpr int32_t kFlushes = 5;
665     runSingleFlushTest(sensors, true /* activateSensor */, 1 /* expectedFlushCount */, Result::OK);
666     runFlushTest(sensors, true /* activateSensor */, kFlushes, kFlushes, Result::OK);
667 }
668 
TEST_P(SensorsHidlTest,FlushOneShotSensor)669 TEST_P(SensorsHidlTest, FlushOneShotSensor) {
670     // Find a sensor that is a one-shot sensor
671     std::vector<SensorInfoType> sensors = getOneShotSensors();
672     if (sensors.size() == 0) {
673         return;
674     }
675 
676     runSingleFlushTest(sensors, true /* activateSensor */, 0 /* expectedFlushCount */,
677                        Result::BAD_VALUE);
678 }
679 
TEST_P(SensorsHidlTest,FlushInactiveSensor)680 TEST_P(SensorsHidlTest, FlushInactiveSensor) {
681     // Attempt to find a non-one shot sensor, then a one-shot sensor if necessary
682     std::vector<SensorInfoType> sensors = getNonOneShotSensors();
683     if (sensors.size() == 0) {
684         sensors = getOneShotSensors();
685         if (sensors.size() == 0) {
686             return;
687         }
688     }
689 
690     runSingleFlushTest(sensors, false /* activateSensor */, 0 /* expectedFlushCount */,
691                        Result::BAD_VALUE);
692 }
693 
TEST_P(SensorsHidlTest,Batch)694 TEST_P(SensorsHidlTest, Batch) {
695     if (getSensorsList().size() == 0) {
696         return;
697     }
698 
699     activateAllSensors(false /* enable */);
700     for (const SensorInfoType& sensor : getSensorsList()) {
701         SCOPED_TRACE(::testing::Message()
702                      << " handle=0x" << std::hex << std::setw(8) << std::setfill('0')
703                      << sensor.sensorHandle << std::dec << " type=" << static_cast<int>(sensor.type)
704                      << " name=" << sensor.name);
705 
706         // Call batch on inactive sensor
707         // One shot sensors have minDelay set to -1 which is an invalid
708         // parameter. Use 0 instead to avoid errors.
709         int64_t samplingPeriodNs = extractReportMode(sensor.flags) == SensorFlagBits::ONE_SHOT_MODE
710                                            ? 0
711                                            : sensor.minDelay;
712         ASSERT_EQ(batch(sensor.sensorHandle, samplingPeriodNs, 0 /* maxReportLatencyNs */),
713                   Result::OK);
714 
715         // Activate the sensor
716         activate(sensor.sensorHandle, true /* enabled */);
717 
718         // Call batch on an active sensor
719         ASSERT_EQ(batch(sensor.sensorHandle, sensor.maxDelay, 0 /* maxReportLatencyNs */),
720                   Result::OK);
721     }
722     activateAllSensors(false /* enable */);
723 
724     // Call batch on an invalid sensor
725     SensorInfoType sensor = getSensorsList().front();
726     sensor.sensorHandle = getInvalidSensorHandle();
727     ASSERT_EQ(batch(sensor.sensorHandle, sensor.minDelay, 0 /* maxReportLatencyNs */),
728               Result::BAD_VALUE);
729 }
730 
TEST_P(SensorsHidlTest,Activate)731 TEST_P(SensorsHidlTest, Activate) {
732     if (getSensorsList().size() == 0) {
733         return;
734     }
735 
736     // Verify that sensor events are generated when activate is called
737     for (const SensorInfoType& sensor : getSensorsList()) {
738         SCOPED_TRACE(::testing::Message()
739                      << " handle=0x" << std::hex << std::setw(8) << std::setfill('0')
740                      << sensor.sensorHandle << std::dec << " type=" << static_cast<int>(sensor.type)
741                      << " name=" << sensor.name);
742 
743         batch(sensor.sensorHandle, sensor.minDelay, 0 /* maxReportLatencyNs */);
744         ASSERT_EQ(activate(sensor.sensorHandle, true), Result::OK);
745 
746         // Call activate on a sensor that is already activated
747         ASSERT_EQ(activate(sensor.sensorHandle, true), Result::OK);
748 
749         // Deactivate the sensor
750         ASSERT_EQ(activate(sensor.sensorHandle, false), Result::OK);
751 
752         // Call deactivate on a sensor that is already deactivated
753         ASSERT_EQ(activate(sensor.sensorHandle, false), Result::OK);
754     }
755 
756     // Attempt to activate an invalid sensor
757     int32_t invalidHandle = getInvalidSensorHandle();
758     ASSERT_EQ(activate(invalidHandle, true), Result::BAD_VALUE);
759     ASSERT_EQ(activate(invalidHandle, false), Result::BAD_VALUE);
760 }
761 
TEST_P(SensorsHidlTest,NoStaleEvents)762 TEST_P(SensorsHidlTest, NoStaleEvents) {
763     constexpr std::chrono::milliseconds kFiveHundredMs(500);
764     constexpr std::chrono::milliseconds kOneSecond(1000);
765 
766     // Register the callback to receive sensor events
767     EventCallback callback;
768     getEnvironment()->registerCallback(&callback);
769 
770     // This test is not valid for one-shot, on-change or special-report-mode sensors
771     const std::vector<SensorInfoType> sensors = getNonOneShotAndNonOnChangeAndNonSpecialSensors();
772     std::chrono::milliseconds maxMinDelay(0);
773     for (const SensorInfoType& sensor : sensors) {
774         std::chrono::milliseconds minDelay = duration_cast<std::chrono::milliseconds>(
775                 std::chrono::microseconds(sensor.minDelay));
776         maxMinDelay = std::chrono::milliseconds(std::max(maxMinDelay.count(), minDelay.count()));
777     }
778 
779     // Activate the sensors so that they start generating events
780     activateAllSensors(true);
781 
782     // According to the CDD, the first sample must be generated within 400ms + 2 * sample_time
783     // and the maximum reporting latency is 100ms + 2 * sample_time. Wait a sufficient amount
784     // of time to guarantee that a sample has arrived.
785     callback.waitForEvents(sensors, kFiveHundredMs + (5 * maxMinDelay));
786     activateAllSensors(false);
787 
788     // Save the last received event for each sensor
789     std::map<int32_t, int64_t> lastEventTimestampMap;
790     for (const SensorInfoType& sensor : sensors) {
791         SCOPED_TRACE(::testing::Message()
792                      << " handle=0x" << std::hex << std::setw(8) << std::setfill('0')
793                      << sensor.sensorHandle << std::dec << " type=" << static_cast<int>(sensor.type)
794                      << " name=" << sensor.name);
795 
796         if (callback.getEvents(sensor.sensorHandle).size() >= 1) {
797             lastEventTimestampMap[sensor.sensorHandle] =
798                     callback.getEvents(sensor.sensorHandle).back().timestamp;
799         }
800     }
801 
802     // Allow some time to pass, reset the callback, then reactivate the sensors
803     usleep(duration_cast<std::chrono::microseconds>(kOneSecond + (5 * maxMinDelay)).count());
804     callback.reset();
805     activateAllSensors(true);
806     callback.waitForEvents(sensors, kFiveHundredMs + (5 * maxMinDelay));
807     activateAllSensors(false);
808 
809     getEnvironment()->unregisterCallback();
810 
811     for (const SensorInfoType& sensor : sensors) {
812         SCOPED_TRACE(::testing::Message()
813                      << " handle=0x" << std::hex << std::setw(8) << std::setfill('0')
814                      << sensor.sensorHandle << std::dec << " type=" << static_cast<int>(sensor.type)
815                      << " name=" << sensor.name);
816 
817         // Skip sensors that did not previously report an event
818         if (lastEventTimestampMap.find(sensor.sensorHandle) == lastEventTimestampMap.end()) {
819             continue;
820         }
821 
822         // Skip sensors with no events
823         const std::vector<EventType> events = callback.getEvents(sensor.sensorHandle);
824         if (events.empty()) {
825             continue;
826         }
827 
828         // Ensure that the first event received is not stale by ensuring that its timestamp is
829         // sufficiently different from the previous event
830         const EventType newEvent = events.front();
831         std::chrono::milliseconds delta = duration_cast<std::chrono::milliseconds>(
832                 nanoseconds(newEvent.timestamp - lastEventTimestampMap[sensor.sensorHandle]));
833         std::chrono::milliseconds sensorMinDelay = duration_cast<std::chrono::milliseconds>(
834                 std::chrono::microseconds(sensor.minDelay));
835         ASSERT_GE(delta, kFiveHundredMs + (3 * sensorMinDelay));
836     }
837 }
838 
checkRateLevel(const SensorInfoType & sensor,int32_t directChannelHandle,RateLevel rateLevel)839 void SensorsHidlTest::checkRateLevel(const SensorInfoType& sensor, int32_t directChannelHandle,
840                                      RateLevel rateLevel) {
841     configDirectReport(sensor.sensorHandle, directChannelHandle, rateLevel,
842                        [&](Result result, int32_t reportToken) {
843                            SCOPED_TRACE(::testing::Message()
844                                         << " handle=0x" << std::hex << std::setw(8)
845                                         << std::setfill('0') << sensor.sensorHandle << std::dec
846                                         << " type=" << static_cast<int>(sensor.type)
847                                         << " name=" << sensor.name);
848 
849                            if (isDirectReportRateSupported(sensor, rateLevel)) {
850                                ASSERT_EQ(result, Result::OK);
851                                if (rateLevel != RateLevel::STOP) {
852                                    ASSERT_GT(reportToken, 0);
853                                }
854                            } else {
855                                ASSERT_EQ(result, Result::BAD_VALUE);
856                            }
857                        });
858 }
859 
queryDirectChannelSupport(SharedMemType memType,bool * supportsSharedMemType,bool * supportsAnyDirectChannel)860 void SensorsHidlTest::queryDirectChannelSupport(SharedMemType memType, bool* supportsSharedMemType,
861                                                 bool* supportsAnyDirectChannel) {
862     *supportsSharedMemType = false;
863     *supportsAnyDirectChannel = false;
864     for (const SensorInfoType& curSensor : getSensorsList()) {
865         if (isDirectChannelTypeSupported(curSensor, memType)) {
866             *supportsSharedMemType = true;
867         }
868         if (isDirectChannelTypeSupported(curSensor, SharedMemType::ASHMEM) ||
869             isDirectChannelTypeSupported(curSensor, SharedMemType::GRALLOC)) {
870             *supportsAnyDirectChannel = true;
871         }
872 
873         if (*supportsSharedMemType && *supportsAnyDirectChannel) {
874             break;
875         }
876     }
877 }
878 
verifyRegisterDirectChannel(std::shared_ptr<SensorsTestSharedMemory<SensorTypeVersion,EventType>> mem,int32_t * directChannelHandle,bool supportsSharedMemType,bool supportsAnyDirectChannel)879 void SensorsHidlTest::verifyRegisterDirectChannel(
880         std::shared_ptr<SensorsTestSharedMemory<SensorTypeVersion, EventType>> mem,
881         int32_t* directChannelHandle, bool supportsSharedMemType, bool supportsAnyDirectChannel) {
882     char* buffer = mem->getBuffer();
883     size_t size = mem->getSize();
884 
885     if (supportsSharedMemType) {
886         memset(buffer, 0xff, size);
887     }
888 
889     registerDirectChannel(mem->getSharedMemInfo(), [&](Result result, int32_t channelHandle) {
890         if (supportsSharedMemType) {
891             ASSERT_EQ(result, Result::OK);
892             ASSERT_GT(channelHandle, 0);
893 
894             // Verify that the memory has been zeroed
895             for (size_t i = 0; i < mem->getSize(); i++) {
896                 ASSERT_EQ(buffer[i], 0x00);
897             }
898         } else {
899             Result expectedResult =
900                     supportsAnyDirectChannel ? Result::BAD_VALUE : Result::INVALID_OPERATION;
901             ASSERT_EQ(result, expectedResult);
902             ASSERT_EQ(channelHandle, -1);
903         }
904         *directChannelHandle = channelHandle;
905     });
906 }
907 
verifyConfigure(const SensorInfoType & sensor,SharedMemType memType,int32_t directChannelHandle,bool supportsAnyDirectChannel)908 void SensorsHidlTest::verifyConfigure(const SensorInfoType& sensor, SharedMemType memType,
909                                       int32_t directChannelHandle, bool supportsAnyDirectChannel) {
910     SCOPED_TRACE(::testing::Message()
911                  << " handle=0x" << std::hex << std::setw(8) << std::setfill('0')
912                  << sensor.sensorHandle << std::dec << " type=" << static_cast<int>(sensor.type)
913                  << " name=" << sensor.name);
914 
915     if (isDirectChannelTypeSupported(sensor, memType)) {
916         // Verify that each rate level is properly supported
917         checkRateLevel(sensor, directChannelHandle, RateLevel::NORMAL);
918         checkRateLevel(sensor, directChannelHandle, RateLevel::FAST);
919         checkRateLevel(sensor, directChannelHandle, RateLevel::VERY_FAST);
920         checkRateLevel(sensor, directChannelHandle, RateLevel::STOP);
921 
922         // Verify that a sensor handle of -1 is only acceptable when using RateLevel::STOP
923         configDirectReport(-1 /* sensorHandle */, directChannelHandle, RateLevel::NORMAL,
924                            [](Result result, int32_t /* reportToken */) {
925                                ASSERT_EQ(result, Result::BAD_VALUE);
926                            });
927         configDirectReport(
928                 -1 /* sensorHandle */, directChannelHandle, RateLevel::STOP,
929                 [](Result result, int32_t /* reportToken */) { ASSERT_EQ(result, Result::OK); });
930     } else {
931         // directChannelHandle will be -1 here, HAL should either reject it as a bad value if there
932         // is some level of direct channel report, otherwise return INVALID_OPERATION if direct
933         // channel is not supported at all
934         Result expectedResult =
935                 supportsAnyDirectChannel ? Result::BAD_VALUE : Result::INVALID_OPERATION;
936         configDirectReport(sensor.sensorHandle, directChannelHandle, RateLevel::NORMAL,
937                            [expectedResult](Result result, int32_t /* reportToken */) {
938                                ASSERT_EQ(result, expectedResult);
939                            });
940     }
941 }
942 
verifyUnregisterDirectChannel(int32_t directChannelHandle,bool supportsAnyDirectChannel)943 void SensorsHidlTest::verifyUnregisterDirectChannel(int32_t directChannelHandle,
944                                                     bool supportsAnyDirectChannel) {
945     Result expectedResult = supportsAnyDirectChannel ? Result::OK : Result::INVALID_OPERATION;
946     ASSERT_EQ(unregisterDirectChannel(directChannelHandle), expectedResult);
947 }
948 
verifyDirectChannel(SharedMemType memType)949 void SensorsHidlTest::verifyDirectChannel(SharedMemType memType) {
950     constexpr size_t kNumEvents = 1;
951     constexpr size_t kMemSize = kNumEvents * kEventSize;
952 
953     std::shared_ptr<SensorsTestSharedMemory<SensorTypeVersion, EventType>> mem(
954             SensorsTestSharedMemory<SensorTypeVersion, EventType>::create(memType, kMemSize));
955     ASSERT_NE(mem, nullptr);
956 
957     bool supportsSharedMemType;
958     bool supportsAnyDirectChannel;
959     queryDirectChannelSupport(memType, &supportsSharedMemType, &supportsAnyDirectChannel);
960 
961     for (const SensorInfoType& sensor : getSensorsList()) {
962         int32_t directChannelHandle = 0;
963         verifyRegisterDirectChannel(mem, &directChannelHandle, supportsSharedMemType,
964                                     supportsAnyDirectChannel);
965         verifyConfigure(sensor, memType, directChannelHandle, supportsAnyDirectChannel);
966         verifyUnregisterDirectChannel(directChannelHandle, supportsAnyDirectChannel);
967     }
968 }
969 
TEST_P(SensorsHidlTest,DirectChannelAshmem)970 TEST_P(SensorsHidlTest, DirectChannelAshmem) {
971     verifyDirectChannel(SharedMemType::ASHMEM);
972 }
973 
TEST_P(SensorsHidlTest,DirectChannelGralloc)974 TEST_P(SensorsHidlTest, DirectChannelGralloc) {
975     verifyDirectChannel(SharedMemType::GRALLOC);
976 }
977 
getDirectChannelSensor(SensorInfoType * sensor,SharedMemType * memType,RateLevel * rate)978 bool SensorsHidlTest::getDirectChannelSensor(SensorInfoType* sensor, SharedMemType* memType,
979                                              RateLevel* rate) {
980     bool found = false;
981     for (const SensorInfoType& curSensor : getSensorsList()) {
982         if (isDirectChannelTypeSupported(curSensor, SharedMemType::ASHMEM)) {
983             *memType = SharedMemType::ASHMEM;
984             *sensor = curSensor;
985             found = true;
986             break;
987         } else if (isDirectChannelTypeSupported(curSensor, SharedMemType::GRALLOC)) {
988             *memType = SharedMemType::GRALLOC;
989             *sensor = curSensor;
990             found = true;
991             break;
992         }
993     }
994 
995     if (found) {
996         // Find a supported rate level
997         constexpr int kNumRateLevels = 3;
998         RateLevel rates[kNumRateLevels] = {RateLevel::NORMAL, RateLevel::FAST,
999                                            RateLevel::VERY_FAST};
1000         *rate = RateLevel::STOP;
1001         for (int i = 0; i < kNumRateLevels; i++) {
1002             if (isDirectReportRateSupported(*sensor, rates[i])) {
1003                 *rate = rates[i];
1004             }
1005         }
1006 
1007         // At least one rate level must be supported
1008         EXPECT_NE(*rate, RateLevel::STOP);
1009     }
1010     return found;
1011 }
1012