crypto: qat - replace avg_array() with a better function
Subsystems (2)
PATCH 1/1 crypto: qat - replace avg_array() with a better function
From: David Laight <[email protected]>
avg_array() is defined as a 'type independant' #define. However the algorithm is only valid for unsigned types and the implementation is only valid for u64.
All the callers pass temporary kmalloc() allocated arrays of u64.
Replace with a function that takes a pointer to a u64 array.
Change the implementation to sum the low and high 32bits of each value separately and then compute the average.
This will be massively faster as it does two divisions rather than one for each element.
Also removes some very pointless __unqual_scalar_typeof(). They could be 'auto _x = 0 ? x + 0 : 0;' even if the types weren't fixed.
Only compile tested.
--- .../intel/qat/qat_common/adf_tl_debugfs.c | 38 ++++++++----------- 1 file changed, 15 insertions(+), 23 deletions(-)
drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c +15 -23
@@ -77,32 +77,24 @@ static int tl_collect_values_u64(struct adf_telemetry *telemetry,* @len: Number of elements. * * This algorithm computes average of an array without running into overflow. +* (Provided len is less than 2 << 31.) * * Return: average of values. */ -#define avg_array (array, len) ( \ -{ \ - typeof(&(array)[0]) _array = (array); \ - __unqual_scalar_typeof(_array[0]) _x = 0; \ - __unqual_scalar_typeof(_array[0]) _y = 0; \ - __unqual_scalar_typeof(_array[0]) _a, _b; \ - typeof(len) _len = (len); \ - size_t _i; \ - \ - for (_i = 0; _i < _len; _i++) { \ - _a = _array[_i]; \ - _b = do_div(_a, _len); \ - _x += _a; \ - if (_y >= _len - _b) { \ - _x++; \ - _y -= _len - _b; \ - } else { \ - _y += _b; \ - } \ - } \ - do_div(_y, _len); \ - (_x + _y); \ -}) +static u64 avg_array (const u64 *array,size_t len) +{ +u64 sum_hi =0 , sum_lo =0 ; +size_t i; + +for (i =0 ; i < len; i++) { + sum_hi += array[i] >>32 ; + sum_lo += (u32 )array[i]; + } + + sum_lo += (u64 )do_div (sum_hi, len) <<32 ; + +return (sum_hi <<32 ) +div_u64 (sum_lo, len); +}/* Calculation function for simple counter. */ static int tl_calc_count(struct adf_telemetry *telemetry,
Signature · 1 line
2.39.5
On Fri, 6 Feb 2026 21:09:40 +0000
[email protected] wrote:
Cc the people discussing unqual_scalar_typeof() for arm64 LTO READ_ONCE().
Quoted 76 lines
From: David Laight <[email protected]>
avg_array()is defined as a 'type independant' #define. However the algorithm is only valid for unsigned types and the implementation is only valid for u64.
All the callers pass temporarykmalloc()allocated arrays of u64.Replace with a function that takes a pointer to a u64 array.
Change the implementation to sum the low and high 32bits of each value separately and then compute the average.
This will be massively faster as it does two divisions rather than one for each element.Also removes some very pointless
__unqual_scalar_typeof(). They could be 'auto _x = 0 ? x + 0 : 0;' even if the types weren't fixed.Only compile tested.
Signed-off-by David Laight <[email protected]>--- .../intel/qat/qat_common/adf_tl_debugfs.c | 38 ++++++++----------- 1 file changed, 15 insertions(+), 23 deletions(-)drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c +15
-23@@ -77,32 +77,24 @@ static int tl_collect_values_u64(struct adf_telemetry *telemetry,* @len: Number of elements. * * This algorithm computes average of an array without running into overflow. +* (Provided len is less than 2 << 31.) * * Return: average of values. */ -#define avg_array (array, len) ( \ -{ \ - typeof(&(array)[0]) _array = (array); \ - __unqual_scalar_typeof(_array[0]) _x = 0; \ - __unqual_scalar_typeof(_array[0]) _y = 0; \ - __unqual_scalar_typeof(_array[0]) _a, _b; \ - typeof(len) _len = (len); \ - size_t _i; \ - \ - for (_i = 0; _i < _len; _i++) { \ - _a = _array[_i]; \ - _b = do_div(_a, _len); \ - _x += _a; \ - if (_y >= _len - _b) { \ - _x++; \ - _y -= _len - _b; \ - } else { \ - _y += _b; \ - } \ - } \ - do_div(_y, _len); \ - (_x + _y); \ -}) +static u64 avg_array (const u64 *array,size_t len) +{ +u64 sum_hi =0 , sum_lo =0 ; +size_t i; + +for (i =0 ; i < len; i++) { + sum_hi += array[i] >>32 ; + sum_lo += (u32 )array[i]; + } + + sum_lo += (u64 )do_div (sum_hi, len) <<32 ; + +return (sum_hi <<32 ) +div_u64 (sum_lo, len); +}/* Calculation function for simple counter. */ static int tl_calc_count(struct adf_telemetry *telemetry,
Giovanni Cabiddu
maintainerQuoted 11 lines · On Fri, Feb 06, 2026 at 09:09:40PM +0000, [email protected] wrote:
From: David Laight <[email protected]>
avg_array()is defined as a 'type independant' #define. However the algorithm is only valid for unsigned types and the implementation is only valid for u64.
All the callers pass temporarykmalloc()allocated arrays of u64.Replace with a function that takes a pointer to a u64 array.
Change the implementation to sum the low and high 32bits of each value separately and then compute the average.
Thanks David, this is a great optimization.
I also reviewed the algorithm and confirmed it is functionally equivalent to the previous version. I tested it on a platform with QAT and it behaves as expected.
Some minor comments below.
Quoted 2 lines
This will be massively faster as it does two divisions rather than one for each element.
NIT: probably not massively faster as the maximum value for len in the current implementation is 4.
Quoted 15 lines
Also removes some very pointless
__unqual_scalar_typeof(). They could be 'auto _x = 0 ? x + 0 : 0;' even if the types weren't fixed.Only compile tested.
Signed-off-by David Laight <[email protected]>--- .../intel/qat/qat_common/adf_tl_debugfs.c | 38 ++++++++----------- 1 file changed, 15 insertions(+), 23 deletions(-)drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c +0
-0
drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c static int tl_collect_values_u64(struct adf_telemetry *telemetry, · line 80
Quoted 4 lines
drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c +1
-0@@ -77,32 +77,24 @@ static int tl_collect_values_u64(struct adf_telemetry *telemetry,* @len: Number of elements. * * This algorithm computes average of an array without running into overflow. +* (Provided len is less than 2 << 31.)
Should this be 2^31 or 1 << 31?
Alternatively: Provided len fits in u32?
Quoted 17 lines
drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c +0
-14* * Return: average of values. */ -#define avg_array (array, len) ( \ -{ \ - typeof(&(array)[0]) _array = (array); \ - __unqual_scalar_typeof(_array[0]) _x = 0; \ - __unqual_scalar_typeof(_array[0]) _y = 0; \ - __unqual_scalar_typeof(_array[0]) _a, _b; \ - typeof(len) _len = (len); \ - size_t _i; \ - \ - for (_i = 0; _i < _len; _i++) { \ - _a = _array[_i]; \ - _b = do_div(_a, _len); \ - _x += _a; \ - if (_y >= _len - _b) { \
drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c static int tl_collect_values_u64(struct adf_telemetry *telemetry, · line 84
Quoted 10 lines
drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c +1
-9- _x++; \ - _y -= _len - _b; \ - }else { \ - _y += _b; \ - } \ - } \ -do_div (_y, _len); \ - (_x + _y); \ -}) +static u64 avg_array (const u64 *array,size_t len)
Shall size_t len be u32 len?
Quoted 6 lines
drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c +6
-0+{ +u64 sum_hi =0 , sum_lo =0 ; +size_t i; + +for (i =0 ; i < len; i++) { + sum_hi += array[i] >>32 ;
drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c static int tl_collect_values_u64(struct adf_telemetry *telemetry, · line 100
Quoted 10 lines
drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c +7
-0+ sum_lo += (u32 )array[i]; + } + + sum_lo += (u64 )do_div (sum_hi, len) <<32 ; + +return (sum_hi <<32 ) +div_u64 (sum_lo, len); +}/* Calculation function for simple counter. */ static int tl_calc_count(struct adf_telemetry *telemetry,
Thanks,
Signature · 1 line
Giovanni
Quoted 18 lines · On Tue, 24 Feb 2026 18:11:37 +0000 Giovanni Cabiddu…
Quoted 11 lines · On Fri, Feb 06, 2026 at 09:09:40PM +0000, [email protected] wrote:
From: David Laight <[email protected]>
avg_array()is defined as a 'type independant' #define. However the algorithm is only valid for unsigned types and the implementation is only valid for u64.
All the callers pass temporarykmalloc()allocated arrays of u64.Replace with a function that takes a pointer to a u64 array.
Change the implementation to sum the low and high 32bits of each value separately and then compute the average.
Thanks David, this is a great optimization.
I also reviewed the algorithm and confirmed it is functionally equivalent to the previous version. I tested it on a platform with QAT and it behaves as expected.
Quoted 6 lines
Some minor comments below.
Quoted 2 lines
This will be massively faster as it does two divisions rather than one for each element.
NIT: probably not
massively fasteras the maximum value for len in the current implementation is 4.
It is still a lot faster - but probably not significant to system performance.
Actually if the max for len is 65536 you can do better (esp. for 32bit). Instead of splitting 32/32 split 48/16, then sum_lo needs only be u32.
giving:
{
u64 sum_hi = 0;
u32 sum_lo = 0;
size_t i;
for (i = 0; i < len; i++) {
sum_hi += array[i] >> 16;
sum_lo += array[i] & 0xffff;
}
sum_lo += do_div(sum_hi, len) << 16;
return (sum_hi << 16) + sum_lo / len;
}OTOH aren't those values performance counts of some kind? Adding four of them together isn't going to wrap.
Quoted 11 lines
Quoted 11 lines
Also removes some very pointless
__unqual_scalar_typeof(). They could be 'auto _x = 0 ? x + 0 : 0;' even if the types weren't fixed.Only compile tested.
Signed-off-by David Laight <[email protected]>--- .../intel/qat/qat_common/adf_tl_debugfs.c | 38 ++++++++----------- 1 file changed, 15 insertions(+), 23 deletions(-)
Quoted 11 lines
drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c static int tl_collect_values_u64(struct adf_telemetry *telemetry, · line 80
Quoted 9 lines
drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c +1
-0@@ -77,32 +77,24 @@ static int tl_collect_values_u64(struct adf_telemetry *telemetry,* @len: Number of elements. * * This algorithm computes average of an array without running into overflow. +* (Provided len is less than 2 << 31.) Should this be 2^31 or 1 << 31?
Alternatively:Provided len fits in u32?
Not sure why I wrote 2 << 31 :-)
The condition is that sum_lo must not overflow.
The worst case is all the low bits being 1.
If len is 2^32 then sum_lo is then (2^32 - 1) * 2^32.
The remainder from the sum_hi divide is shifted and added in, giving (2^32 - 1) * (2^32 + 1) which is what my maths teacher called a 'cow and goat' - (cow + goat) * (cow - goat) = cow squared - goat squared, so then maximum for sum_lo is 2^64 - 1 which fits.
Which means it should have been 'len <= 2^32'.
David
Quoted 49 lines
Quoted 18 lines
drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c +0
-14* * Return: average of values. */ -#define avg_array (array, len) ( \ -{ \ - typeof(&(array)[0]) _array = (array); \ - __unqual_scalar_typeof(_array[0]) _x = 0; \ - __unqual_scalar_typeof(_array[0]) _y = 0; \ - __unqual_scalar_typeof(_array[0]) _a, _b; \ - typeof(len) _len = (len); \ - size_t _i; \ - \ - for (_i = 0; _i < _len; _i++) { \ - _a = _array[_i]; \ - _b = do_div(_a, _len); \ - _x += _a; \ - if (_y >= _len - _b) { \drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c static int tl_collect_values_u64(struct adf_telemetry *telemetry, · line 84
Quoted 10 lines
drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c +1
-9- _x++; \ - _y -= _len - _b; \ - }else { \ - _y += _b; \ - } \ - } \ -do_div (_y, _len); \ - (_x + _y); \ -}) +static u64 avg_array (const u64 *array,size_t len)Shall
size_tlen be u32 len?Quoted 6 lines
drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c +6
-0+{ +u64 sum_hi =0 , sum_lo =0 ; +size_t i; + +for (i =0 ; i < len; i++) { + sum_hi += array[i] >>32 ;drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c static int tl_collect_values_u64(struct adf_telemetry *telemetry, · line 100
Quoted 10 lines
drivers/crypto/intel/qat/qat_common/adf_tl_debugfs.c +7
-0+ sum_lo += (u32 )array[i]; + } + + sum_lo += (u64 )do_div (sum_hi, len) <<32 ; + +return (sum_hi <<32 ) +div_u64 (sum_lo, len); +}/* Calculation function for simple counter. */ static int tl_calc_count(struct adf_telemetry *telemetry,Thanks,