platform/chrome: sensorhub: Implement quickselect for median calculation

The cros_ec_sensor_ring_median function currently uses an inefficient
sorting algorithm (> O(n)) to find the median of an array. This patch
replaces the sorting approach with the quickselect algorithm, which
achieves an average time complexity of O(n).

The algorithm employs the median-of-three rule to select the pivot,
mitigating worst-case scenarios and reducing the expected number of
necessary comparisons. This strategy enhances the algorithm's
efficiency and ensures a more balanced partitioning.

In the worst case, the runtime of quickselect could regress to O(n^2).
To address this, alternative algorithms like median-of-medians that
can guarantee O(n) even in the worst case. However, due to higher
overhead and increased complexity of implementation, quickselect
remains a pragmatic choice for our use case.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
Link: https://lore.kernel.org/r/20231110165314.1559285-1-visitorckw@gmail.com
Signed-off-by: Tzung-Bi Shih <tzungbi@kernel.org>

platform/chrome: sensorhub: Fix typos

Replace 'preceeds' with 'precedes' in the comment.
Replace 'porod' with 'period' in the comment.
Replace 'noone' with 'no one' in the comment.
Replace 'lantency' with 'latency' in the comment.
Replace 'kifo' with 'kfifo' in the comment.
Replace 'change' with 'chance' in the comment.

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
Reviewed-by: Randy Dunlap <rdunlap@infradead.org>
Link: https://lore.kernel.org/r/20231110165239.1559109-1-visitorckw@gmail.com
Signed-off-by: Tzung-Bi Shih <tzungbi@kernel.org>

platform: chrome: Split trace include file

cros_ec_trace.h defined 5 tracing events, 2 for cros_ec_proto and
3 for cros_ec_sensorhub_ring.
These 2 files are in different kernel modules, the traces are defined
twice in the kernel which leads to problem enabling only some traces.

Move sensorhub traces from cros_ec_trace.h to cros_ec_sensorhub_trace.h
and enable them only in cros_ec_sensorhub kernel module.

Check we can now enable any single traces: without this patch,
we can only enable all sensorhub traces or none.

Fixes: d453ceb6549a ("platform/chrome: sensorhub: Add trace events for sample")

Signed-off-by: Gwendal Grignou <gwendal@chromium.org>
Cc: stable@vger.kernel.org
Link: https://lore.kernel.org/r/20220122001301.640337-1-gwendal@chromium.org
Signed-off-by: Benson Leung <bleung@chromium.org>

platform/chrome: sensorhub: Add trace events for sample

Add trace event to report samples and their timestamp coming from the
EC. It allows to check if the timestamps are correct and the filter is
working correctly without introducing too much latency.

To enable these events:

cd /sys/kernel/debug/tracing/
echo 1 > events/cros_ec/enable
echo 0 > events/cros_ec/cros_ec_request_start/enable
echo 0 > events/cros_ec/cros_ec_request_done/enable
echo 1 > tracing_on
cat trace_pipe
Observe event flowing:
irq/105-chromeo-95 [000] .... 613.659758: cros_ec_sensorhub_timestamp: ...
irq/105-chromeo-95 [000] .... 613.665219: cros_ec_sensorhub_filter: dx: ...

Signed-off-by: Gwendal Grignou <gwendal@chromium.org>
Signed-off-by: Enric Balletbo i Serra <enric.balletbo@collabora.com>

platform/chrome: cros_ec_sensorhub: Simplify legacy timestamp spreading

On some machines (nami), interrupt latency cause samples to appear
to be from the future and are pegged to the current time.
We would see samples with this pattern:

[t, t + ~5ms, t + ~10ms, t + ~10ms + 100us, t + ~10ms + 200us],
(current now) (current now)
(t is the last timestamp time)

Last 2 samples would be barely spread, causing applications to
complain.

We now spread the entire sequence. This is not great: in the example
the sensor was supposed to send samples every 5ms, it now appears to
send one every 2.5ms, but it is slightly closer to reality:

sampling time in the example above
At sensor level

1 2 3 4 5
+-----5ms-----+-----5ms-----+-----5ms-----+----5ms-----+---> t

Before, at host level
1 2 3 4 5
--interrupt delay------+-----5ms-----+-----5ms-----+-+-+---> t

Afer, at host level
1 2 3 4 5
--interrupt delay------+-2.5ms-+-2.5ms-+-2.5ms-+-2.5ms-+---> t

Signed-off-by: Gwendal Grignou <gwendal@chromium.org>
Signed-off-by: Enric Balletbo i Serra <enric.balletbo@collabora.com>

platform/chrome: cros_ec_sensorhub: Fix EC timestamp overflow

EC is using 32 bit timestamps (us), and before converting it to 64bit
they were not casted, so it would overflow every 4s.
Regular overflow every ~70 minutes was not taken into account either.

Signed-off-by: Gwendal Grignou <gwendal@chromium.org>
Signed-off-by: Enric Balletbo i Serra <enric.balletbo@collabora.com>

platform/chrome: cros_ec_sensorhub: Allocate sensorhub resource before claiming sensors

Allocate callbacks array before enumerating the sensors: The probe routine
for these sensors (for instance cros_ec_sensors_probe) can be called
within the sensorhub probe routine (cros_ec_sensors_probe())

Fixes: 145d59baff594 ("platform/chrome: cros_ec_sensorhub: Add FIFO support")
Signed-off-by: Gwendal Grignou <gwendal@chromium.org>
Reported-by: Douglas Anderson <dianders@chromium.org>
Tested-by: Douglas Anderson <dianders@chromium.org>
Signed-off-by: Enric Balletbo i Serra <enric.balletbo@collabora.com>

platform/chrome: cros_ec_sensorhub: Add missing '\n' in log messages

Message logged by 'dev_xxx()' or 'pr_xxx()' should end with a '\n'.

Fixes: 145d59baff59 ("platform/chrome: cros_ec_sensorhub: Add FIFO support")
Signed-off-by: Christophe JAILLET <christophe.jaillet@wanadoo.fr>
Signed-off-by: Enric Balletbo i Serra <enric.balletbo@collabora.com>

platform/chrome: cros_ec_sensorhub: Off by one in cros_sensorhub_send_sample()

The sensorhub->push_data[] array has sensorhub->sensor_num elements.
It's allocated in cros_ec_sensorhub_ring_add(). So the > should be >=
to prevent a read one element beyond the end of the array.

Fixes: 145d59baff59 ("platform/chrome: cros_ec_sensorhub: Add FIFO support")
Signed-off-by: Dan Carpenter <dan.carpenter@oracle.com>
Reviewed-by: Guenter Roeck <groeck@chromium.org>
Signed-off-by: Enric Balletbo i Serra <enric.balletbo@collabora.com>

platform/chrome: cros_ec_sensorhub: Add median filter

Events are timestamped in EC time space, their timestamps need to be
converted in host time space.

The assumption is the time delta between when the interrupt is sent
by the EC and when it is receive by the host is a [small] constant.
This is not always true, even with hard-wired interrupt. To mitigate
worst offenders, add a median filter to weed out bigger than expected
delays.

Signed-off-by: Gwendal Grignou <gwendal@chromium.org>
Acked-by: Jonathan Cameron <Jonathan.Cameron@huawei.com>
Acked-by: Lee Jones <lee.jones@linaro.org>
Acked-by: Andy Shevchenko <andy.shevchenko@gmail.com>
Signed-off-by: Enric Balletbo i Serra <enric.balletbo@collabora.com>

platform/chrome: cros_ec_sensorhub: Add code to spread timestmap

EC FIFO can send sensor events in batch. Spread them based on
previous (TSa) and currnet timestamp (TSb)

EC FIFO iio events
+-----------+
| TSa |
+-----------+ +---------------------------------------+
| event 1 | | event 1 | TSb - (TSb - TSa)/n * (n-1) |
+-----------+ +---------------------------------------+
| event 2 | | event 2 | TSb - (TSb - TSa)/n * (n-2) |
+-----------+ +---------------------------------------+
| ... | ------> | .... | |
+-----------+ +---------------------------------------+
| event n-1 | | event 2 | TSb - (TSb - TSa)/n |
+-----------+ +---------------------------------------+
| event n | | event 2 | TSb |
+-----------+ +---------------------------------------+
| TSb |
+-----------+

Signed-off-by: Gwendal Grignou <gwendal@chromium.org>
Acked-by: Jonathan Cameron <Jonathan.Cameron@huawei.com>
Acked-by: Lee Jones <lee.jones@linaro.org>
Acked-by: Andy Shevchenko <andy.shevchenko@gmail.com>
Signed-off-by: Enric Balletbo i Serra <enric.balletbo@collabora.com>

platform/chrome: cros_ec_sensorhub: Add FIFO support

cros_ec_sensorhub registers a listener and query motion sense FIFO,
spread to iio sensors registers.

To test, we can use libiio:
iiod&
iio_readdev -u ip:localhost -T 10000 -s 25 -b 16 cros-ec-gyro | od -x

Signed-off-by: Gwendal Grignou <gwendal@chromium.org>
Reviewed-by: Jonathan Cameron <Jonathan.Cameron@huawei.com>
Acked-by: Andy Shevchenko <andy.shevchenko@gmail.com>
Signed-off-by: Enric Balletbo i Serra <enric.balletbo@collabora.com>