From 49e380795414039f7b3bd44c121104f31738dcf1 Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Sat, 11 Nov 2023 00:52:39 +0800 Subject: 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 Reviewed-by: Randy Dunlap Link: https://lore.kernel.org/r/20231110165239.1559109-1-visitorckw@gmail.com Signed-off-by: Tzung-Bi Shih --- drivers/platform/chrome/cros_ec_sensorhub_ring.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/drivers/platform/chrome/cros_ec_sensorhub_ring.c b/drivers/platform/chrome/cros_ec_sensorhub_ring.c index 71948dade0e2..9e17f7483ca0 100644 --- a/drivers/platform/chrome/cros_ec_sensorhub_ring.c +++ b/drivers/platform/chrome/cros_ec_sensorhub_ring.c @@ -103,7 +103,7 @@ EXPORT_SYMBOL_GPL(cros_ec_sensorhub_unregister_push_data); * @sensorhub: Sensor Hub object * @on: true when events are requested. * - * To be called before sleeping or when noone is listening. + * To be called before sleeping or when no one is listening. * Return: 0 on success, or an error when we can not communicate with the EC. * */ @@ -175,8 +175,8 @@ static s64 cros_ec_sensor_ring_median(s64 *array, size_t length) * * While a and b are recorded at accurate times (due to the EC real time * nature); c is pretty untrustworthy, even though it's recorded the - * first thing in ec_irq_handler(). There is a very good change we'll get - * added lantency due to: + * first thing in ec_irq_handler(). There is a very good chance we'll get + * added latency due to: * other irqs * ddrfreq * cpuidle @@ -511,7 +511,7 @@ cros_ec_sensor_ring_process_event(struct cros_ec_sensorhub *sensorhub, * ringbuffer. * * This is the new spreading code, assumes every sample's timestamp - * preceeds the sample. Run if tight_timestamps == true. + * precedes the sample. Run if tight_timestamps == true. * * Sometimes the EC receives only one interrupt (hence timestamp) for * a batch of samples. Only the first sample will have the correct @@ -595,7 +595,7 @@ cros_ec_sensor_ring_spread_add(struct cros_ec_sensorhub *sensorhub, } else { /* * Push first sample in the batch to the, - * kifo, it's guaranteed to be correct, the + * kfifo, it's guaranteed to be correct, the * rest will follow later on. */ sample_idx = 1; @@ -701,7 +701,7 @@ done_with_this_batch: * last_out --> * * - * We spread time for the samples using perod p = (current - TS1)/4. + * We spread time for the samples using period p = (current - TS1)/4. * between TS1 and TS2: [TS1+p/4, TS1+2p/4, TS1+3p/4, current_timestamp]. * */ -- cgit v1.2.3 From d131f1f3b459980d38a59adc3598c96cc3a6ad5e Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Sat, 11 Nov 2023 00:53:14 +0800 Subject: 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 Link: https://lore.kernel.org/r/20231110165314.1559285-1-visitorckw@gmail.com Signed-off-by: Tzung-Bi Shih --- drivers/platform/chrome/cros_ec_sensorhub_ring.c | 62 +++++++++++++++++------- 1 file changed, 45 insertions(+), 17 deletions(-) diff --git a/drivers/platform/chrome/cros_ec_sensorhub_ring.c b/drivers/platform/chrome/cros_ec_sensorhub_ring.c index 9e17f7483ca0..1205219515d6 100644 --- a/drivers/platform/chrome/cros_ec_sensorhub_ring.c +++ b/drivers/platform/chrome/cros_ec_sensorhub_ring.c @@ -133,33 +133,61 @@ int cros_ec_sensorhub_ring_fifo_enable(struct cros_ec_sensorhub *sensorhub, return ret; } -static int cros_ec_sensor_ring_median_cmp(const void *pv1, const void *pv2) +static void cros_ec_sensor_ring_median_swap(s64 *a, s64 *b) { - s64 v1 = *(s64 *)pv1; - s64 v2 = *(s64 *)pv2; - - if (v1 > v2) - return 1; - else if (v1 < v2) - return -1; - else - return 0; + s64 tmp = *a; + *a = *b; + *b = tmp; } /* * cros_ec_sensor_ring_median: Gets median of an array of numbers * - * For now it's implemented using an inefficient > O(n) sort then return - * the middle element. A more optimal method would be something like - * quickselect, but given that n = 64 we can probably live with it in the - * name of clarity. + * It's implemented using the quickselect algorithm, which achieves an + * average time complexity of O(n) the middle element. In the worst case, + * the runtime of quickselect could regress to O(n^2). To mitigate this, + * algorithms like median-of-medians exist, which can guarantee O(n) even + * in the worst case. However, these algorithms come with a higher + * overhead and are more complex to implement, making quickselect a + * pragmatic choice for our use case. * - * Warning: the input array gets modified (sorted)! + * Warning: the input array gets modified! */ static s64 cros_ec_sensor_ring_median(s64 *array, size_t length) { - sort(array, length, sizeof(s64), cros_ec_sensor_ring_median_cmp, NULL); - return array[length / 2]; + int lo = 0; + int hi = length - 1; + + while (lo <= hi) { + int mid = lo + (hi - lo) / 2; + int pivot, i; + + if (array[lo] > array[mid]) + cros_ec_sensor_ring_median_swap(&array[lo], &array[mid]); + if (array[lo] > array[hi]) + cros_ec_sensor_ring_median_swap(&array[lo], &array[hi]); + if (array[mid] < array[hi]) + cros_ec_sensor_ring_median_swap(&array[mid], &array[hi]); + + pivot = array[hi]; + i = lo - 1; + + for (int j = lo; j < hi; j++) + if (array[j] < pivot) + cros_ec_sensor_ring_median_swap(&array[++i], &array[j]); + + /* The pivot's index corresponds to i+1. */ + cros_ec_sensor_ring_median_swap(&array[i + 1], &array[hi]); + if (i + 1 == length / 2) + return array[i + 1]; + if (i + 1 > length / 2) + hi = i; + else + lo = i + 2; + } + + /* Should never reach here. */ + return -1; } /* -- cgit v1.2.3 From 59a9ccf19ee03179faf047822bbec76cac7467a4 Mon Sep 17 00:00:00 2001 From: "Gustavo A. R. Silva" Date: Wed, 29 Mar 2023 19:54:02 -0600 Subject: platform/chrome: cros_ec_vbc: Fix -Warray-bounds warnings MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit GCC-13 (and Clang) does not like having a partially allocated object, since it cannot reason about it for bounds checking. Notice that the compiler is legitimately complaining about accessing an object (params, in this case) for which not enough memory was allocated. The object is of size 20 bytes: struct ec_params_vbnvcontext { uint32_t op; /* 0 4 */ uint8_t block[16]; /* 4 16 */ /* size: 20, cachelines: 1, members: 2 */ /* last cacheline: 20 bytes */ }; but only 16 bytes are allocated: sizeof(struct ec_response_vbnvcontext) == 16 In this case, as only enough space for the op field is allocated, we can use an object of type uint32_t instead of a whole struct ec_params_vbnvcontext (for which not enough memory is allocated). Fix the following warning seen under GCC 13: drivers/platform/chrome/cros_ec_vbc.c: In function ‘vboot_context_read’: drivers/platform/chrome/cros_ec_vbc.c:36:15: warning: array subscript ‘struct ec_params_vbnvcontext[1]’ is partly outside array bounds of ‘unsigned char[36]’ [-Warray-bounds=] 36 | params->op = EC_VBNV_CONTEXT_OP_READ; | ^~ In file included from drivers/platform/chrome/cros_ec_vbc.c:12: In function ‘kmalloc’, inlined from ‘vboot_context_read’ at drivers/platform/chrome/cros_ec_vbc.c:30:8: ./include/linux/slab.h:580:24: note: at offset 20 into object of size 36 allocated by ‘kmalloc_trace’ 580 | return kmalloc_trace( | ^~~~~~~~~~~~~~ 581 | kmalloc_caches[kmalloc_type(flags)][index], | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 582 | flags, size); | ~~~~~~~~~~~~ Link: https://github.com/KSPP/linux/issues/278 Signed-off-by: "Gustavo A. R. Silva" Reviewed-by: Kees Cook Link: https://lore.kernel.org/r/ZCTrutoN+9TiJM8u@work Signed-off-by: Tzung-Bi Shih --- drivers/platform/chrome/cros_ec_vbc.c | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/drivers/platform/chrome/cros_ec_vbc.c b/drivers/platform/chrome/cros_ec_vbc.c index 2e4af10c7679..274ea0c64b33 100644 --- a/drivers/platform/chrome/cros_ec_vbc.c +++ b/drivers/platform/chrome/cros_ec_vbc.c @@ -20,10 +20,14 @@ static ssize_t vboot_context_read(struct file *filp, struct kobject *kobj, struct device *dev = kobj_to_dev(kobj); struct cros_ec_dev *ec = to_cros_ec_dev(dev); struct cros_ec_device *ecdev = ec->ec_dev; - struct ec_params_vbnvcontext *params; struct cros_ec_command *msg; + /* + * This should be a pointer to the same type as op field in + * struct ec_params_vbnvcontext. + */ + uint32_t *params_op; int err; - const size_t para_sz = sizeof(params->op); + const size_t para_sz = sizeof(*params_op); const size_t resp_sz = sizeof(struct ec_response_vbnvcontext); const size_t payload = max(para_sz, resp_sz); @@ -32,8 +36,8 @@ static ssize_t vboot_context_read(struct file *filp, struct kobject *kobj, return -ENOMEM; /* NB: we only kmalloc()ated enough space for the op field */ - params = (struct ec_params_vbnvcontext *)msg->data; - params->op = EC_VBNV_CONTEXT_OP_READ; + params_op = (uint32_t *)msg->data; + *params_op = EC_VBNV_CONTEXT_OP_READ; msg->version = EC_VER_VBNV_CONTEXT; msg->command = EC_CMD_VBNV_CONTEXT; -- cgit v1.2.3 From 57eb6dcd32cf6b49c38eff81e60e8fd471aa05a8 Mon Sep 17 00:00:00 2001 From: Christophe JAILLET Date: Sat, 16 Dec 2023 17:59:38 +0100 Subject: platform/chrome/wilco_ec: Remove usage of the deprecated ida_simple_xx() API ida_alloc() and ida_free() should be preferred to the deprecated ida_simple_get() and ida_simple_remove(). This is less verbose. Signed-off-by: Christophe JAILLET Link: https://lore.kernel.org/r/898d9aa181a84f1d17725ca047004bad532c37e9.1702745959.git.christophe.jaillet@wanadoo.fr Signed-off-by: Tzung-Bi Shih --- drivers/platform/chrome/wilco_ec/event.c | 4 ++-- drivers/platform/chrome/wilco_ec/telemetry.c | 6 +++--- 2 files changed, 5 insertions(+), 5 deletions(-) diff --git a/drivers/platform/chrome/wilco_ec/event.c b/drivers/platform/chrome/wilco_ec/event.c index f80a7c83cfba..13291fb4214e 100644 --- a/drivers/platform/chrome/wilco_ec/event.c +++ b/drivers/platform/chrome/wilco_ec/event.c @@ -495,7 +495,7 @@ static int event_device_add(struct acpi_device *adev) free_dev_data: hangup_device(dev_data); free_minor: - ida_simple_remove(&event_ida, minor); + ida_free(&event_ida, minor); return error; } @@ -504,7 +504,7 @@ static void event_device_remove(struct acpi_device *adev) struct event_device_data *dev_data = adev->driver_data; cdev_device_del(&dev_data->cdev, &dev_data->dev); - ida_simple_remove(&event_ida, MINOR(dev_data->dev.devt)); + ida_free(&event_ida, MINOR(dev_data->dev.devt)); hangup_device(dev_data); } diff --git a/drivers/platform/chrome/wilco_ec/telemetry.c b/drivers/platform/chrome/wilco_ec/telemetry.c index 253098bace63..b7c616f3d179 100644 --- a/drivers/platform/chrome/wilco_ec/telemetry.c +++ b/drivers/platform/chrome/wilco_ec/telemetry.c @@ -372,7 +372,7 @@ static int telem_device_probe(struct platform_device *pdev) dev_data = kzalloc(sizeof(*dev_data), GFP_KERNEL); if (!dev_data) { - ida_simple_remove(&telem_ida, minor); + ida_free(&telem_ida, minor); return -ENOMEM; } @@ -393,7 +393,7 @@ static int telem_device_probe(struct platform_device *pdev) error = cdev_device_add(&dev_data->cdev, &dev_data->dev); if (error) { put_device(&dev_data->dev); - ida_simple_remove(&telem_ida, minor); + ida_free(&telem_ida, minor); return error; } @@ -405,7 +405,7 @@ static void telem_device_remove(struct platform_device *pdev) struct telem_device_data *dev_data = platform_get_drvdata(pdev); cdev_device_del(&dev_data->cdev, &dev_data->dev); - ida_simple_remove(&telem_ida, MINOR(dev_data->dev.devt)); + ida_free(&telem_ida, MINOR(dev_data->dev.devt)); put_device(&dev_data->dev); } -- cgit v1.2.3