[LTP] [PATCH v2 0/2] Fix Integer Overflow and Thread Safety in Record Counting

[LTP] [PATCH v2 0/2] Fix Integer Overflow and Thread Safety in Record Counting

[Vishal Chourasia]

I am writing to present a patch set that addresses a significant issue we've
observed in our 64-bit systems. We noticed an integer overflow bug affecting our
results, which has prompted this set of changes.

Key Changes:

- Type Selection for Record Counting: We've shifted from using `unsigned int` to
  `uintptr_t` for tracking record counts. This is crucial, especially on 64-bit
  systems, to avoid potential integer overflows that can jeopardize the accuracy
  of our results. 
  
- Thread Safety for Record Counting: Previously, the design used a global
  `records_read` variable to accumulate counts from different threads. This
  approach didn't employ locks, posing potential race conditions. In this patch,
  we've rectified this by introducing a thread-local variable, `records_thread`,
  to individually store the record count of each thread. The accumulated total
  is then fetched safely during thread joining. 

Rationale:

These changes stem from our observations on certain 64-bit systems. The integer
overflow bug, combined with potential race conditions due to the unguarded
global variable, was impacting the integrity of our results. By switching to
`uintptr_t`, we ensure adequate space to hold larger counts typical for 64-bit
systems. Additionally, by introducing the thread-local variable and removing the
global counter, we've added a level of safety against concurrent access issues.  

This patch set ensures the robustness and accuracy of our system, particularly
in multi-threaded environments on 64-bit platforms.

Thank you for your time and consideration. I am open to any feedback and will
gladly make any necessary modifications. 

Changes in v2:
- Replaced mutex synchronization for global records_read updates with inherent
  serialization offered by pthread_join. 
- Link to v1: https://lore.kernel.org/all/20230814061810.2297146-1-vishalc@linux.ibm.com/

Vishal Chourasia (2):
  Enhance Thread Safety in Record Counting
  ebizzy: prevent integer overflow in 64-bit systems

 utils/benchmark/ebizzy-0.3/ebizzy.c | 20 ++++++++++++--------
 1 file changed, 12 insertions(+), 8 deletions(-)

-- 
2.39.3


-- 
Mailing list info: https://lists.linux.it/listinfo/ltp

[LTP] [PATCH v2 1/2] Enhance Thread Safety in Record Counting

[Vishal Chourasia]

This patch addresses a thread safety concern in record counting. Originally,
the design leveraged a global `records_read` variable to aggregate counts from
different threads. This method was devoid of locks, leading to potential race
conditions. To remedy this:

- Introduced a thread-local variable, `records_thread`, for each thread to
  store its record count.
- Upon thread joining, the accumulated total from each `records_thread` is safely
  captured, ensuring accurate and race-free counting.

The overall change enhances thread safety, especially in multi-threaded
environments, and ensures the correct count is fetched without race conditions.

Signed-off-by: Vishal Chourasia <vishalc@linux.ibm.com>
Reviewed-by: Srikar Dronamraju <srikar@linux.vnet.ibm.com>
Reviewed-by: Shrikanth Hegde <sshegde@linux.vnet.ibm.com>
Reviewed-by: Cyril Hrubis <chrubis@suse.cz>
Suggested-by: Cyril Hrubis <chrubis@suse.cz>
---
 utils/benchmark/ebizzy-0.3/ebizzy.c | 21 +++++++++++++--------
 1 file changed, 13 insertions(+), 8 deletions(-)

diff --git a/utils/benchmark/ebizzy-0.3/ebizzy.c b/utils/benchmark/ebizzy-0.3/ebizzy.c
index 54b047130..ae0981fbd 100644
--- a/utils/benchmark/ebizzy-0.3/ebizzy.c
+++ b/utils/benchmark/ebizzy-0.3/ebizzy.c
@@ -50,6 +50,7 @@
 #include <time.h>
 #include <sys/time.h>
 #include <sys/resource.h>
+#include <stdint.h>
 
 #include "ebizzy.h"
 
@@ -83,7 +84,6 @@ static char **hole_mem;
 static unsigned int page_size;
 static time_t start_time;
 static volatile int threads_go;
-static unsigned int records_read;
 
 static void usage(void)
 {
@@ -366,13 +366,13 @@ static inline unsigned int rand_num(unsigned int max, unsigned int *state)
  *
  */
 
-static unsigned int search_mem(void)
+static uintptr_t search_mem(void)
 {
 	record_t key, *found;
 	record_t *src, *copy;
 	unsigned int chunk;
 	size_t copy_size = chunk_size;
-	unsigned int i;
+	uintptr_t i;
 	unsigned int state = 0;
 
 	for (i = 0; threads_go == 1; i++) {
@@ -423,6 +423,8 @@ static unsigned int search_mem(void)
 
 static void *thread_run(void *arg __attribute__((unused)))
 {
+	uintptr_t records_thread;
+
 	if (verbose > 1)
 		printf("Thread started\n");
 
@@ -430,13 +432,13 @@ static void *thread_run(void *arg __attribute__((unused)))
 
 	while (threads_go == 0) ;
 
-	records_read += search_mem();
+	records_thread = search_mem();
 
 	if (verbose > 1)
 		printf("Thread finished, %f seconds\n",
 		       difftime(time(NULL), start_time));
 
-	return NULL;
+	return (void *)records_thread;
 }
 
 static struct timeval difftimeval(struct timeval *end, struct timeval *start)
@@ -454,6 +456,7 @@ static void start_threads(void)
 	unsigned int i;
 	struct rusage start_ru, end_ru;
 	struct timeval usr_time, sys_time;
+	uintptr_t records_read = 0;
 	int err;
 
 	if (verbose)
@@ -484,18 +487,20 @@ static void start_threads(void)
 	 */
 
 	for (i = 0; i < threads; i++) {
-		err = pthread_join(thread_array[i], NULL);
+		uintptr_t record_thread;
+		err = pthread_join(thread_array[i], (void *)&record_thread);
 		if (err) {
 			fprintf(stderr, "Error joining thread %d\n", i);
 			exit(1);
 		}
+		records_read += record_thread;
 	}
 
 	if (verbose)
 		printf("Threads finished\n");
 
-	printf("%u records/s\n",
-	       (unsigned int)(((double)records_read) / elapsed));
+	printf("%tu records/s\n",
+	       (uintptr_t)(((double)records_read) / elapsed));
 
 	usr_time = difftimeval(&end_ru.ru_utime, &start_ru.ru_utime);
 	sys_time = difftimeval(&end_ru.ru_stime, &start_ru.ru_stime);
-- 
2.39.3


-- 
Mailing list info: https://lists.linux.it/listinfo/ltp

Re: [LTP] [PATCH v2 1/2] Enhance Thread Safety in Record Counting

[Cyril Hrubis]

Hi!
Applied, thanks.

-- 
Cyril Hrubis
chrubis@suse.cz

-- 
Mailing list info: https://lists.linux.it/listinfo/ltp

[LTP] [PATCH v2 2/2] ebizzy: prevent integer overflow in 64-bit systems

[Vishal Chourasia]

By handling the rate computation within the thread joining loop, we've optimized
our storage, ensuring we don't risk integer overflow, particularly in 64-bit
systems. Given that `uintptr_t` can handle values up to `(2^64)-1`, to create an
overflow with the current implementation on a system with 9,000,000,000
records/sec values, one would need to run more than (2^64-1)/9 billion threads,
which is astronomically high and practically impossible.

This change reinforces the reliability of our code on high-performance, 64-bit
systems, ensuring accurate record counting without potential overflows.

In the `start_threads` function of the `ebizzy` benchmark utility, the variable
previously named `records_read` has been refactored to `records_per_sec` to more
accurately reflect its purpose, which is to store the rate of records per
second.

Signed-off-by: Vishal Chourasia <vishalc@linux.ibm.com>
Reviewed-by: Srikar Dronamraju <srikar@linux.vnet.ibm.com>
Reviewed-by: Shrikanth Hegde <sshegde@linux.vnet.ibm.com>
---
 utils/benchmark/ebizzy-0.3/ebizzy.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/utils/benchmark/ebizzy-0.3/ebizzy.c b/utils/benchmark/ebizzy-0.3/ebizzy.c
index ae0981fbd..c3eac1133 100644
--- a/utils/benchmark/ebizzy-0.3/ebizzy.c
+++ b/utils/benchmark/ebizzy-0.3/ebizzy.c
@@ -456,7 +456,7 @@ static void start_threads(void)
 	unsigned int i;
 	struct rusage start_ru, end_ru;
 	struct timeval usr_time, sys_time;
-	uintptr_t records_read = 0;
+	uintptr_t records_per_sec = 0;
 	int err;
 
 	if (verbose)
@@ -493,14 +493,13 @@ static void start_threads(void)
 			fprintf(stderr, "Error joining thread %d\n", i);
 			exit(1);
 		}
-		records_read += record_thread;
+		records_per_sec += (record_thread / elapsed);
 	}
 
 	if (verbose)
 		printf("Threads finished\n");
 
-	printf("%tu records/s\n",
-	       (uintptr_t)(((double)records_read) / elapsed));
+	printf("%tu records/s\n", records_per_sec);
 
 	usr_time = difftimeval(&end_ru.ru_utime, &start_ru.ru_utime);
 	sys_time = difftimeval(&end_ru.ru_stime, &start_ru.ru_stime);
-- 
2.39.3


-- 
Mailing list info: https://lists.linux.it/listinfo/ltp

Re: [LTP] [PATCH v2 2/2] ebizzy: prevent integer overflow in 64-bit systems

[Cyril Hrubis]

Hi!
> Signed-off-by: Vishal Chourasia <vishalc@linux.ibm.com>
> Reviewed-by: Srikar Dronamraju <srikar@linux.vnet.ibm.com>
> Reviewed-by: Shrikanth Hegde <sshegde@linux.vnet.ibm.com>
> ---
>  utils/benchmark/ebizzy-0.3/ebizzy.c | 7 +++----
>  1 file changed, 3 insertions(+), 4 deletions(-)
> 
> diff --git a/utils/benchmark/ebizzy-0.3/ebizzy.c b/utils/benchmark/ebizzy-0.3/ebizzy.c
> index ae0981fbd..c3eac1133 100644
> --- a/utils/benchmark/ebizzy-0.3/ebizzy.c
> +++ b/utils/benchmark/ebizzy-0.3/ebizzy.c
> @@ -456,7 +456,7 @@ static void start_threads(void)
>  	unsigned int i;
>  	struct rusage start_ru, end_ru;
>  	struct timeval usr_time, sys_time;
> -	uintptr_t records_read = 0;
> +	uintptr_t records_per_sec = 0;
>  	int err;
>  
>  	if (verbose)
> @@ -493,14 +493,13 @@ static void start_threads(void)
>  			fprintf(stderr, "Error joining thread %d\n", i);
>  			exit(1);
>  		}
> -		records_read += record_thread;
> +		records_per_sec += (record_thread / elapsed);

This actually introduces quite a bit rounding errors. Note that even
with 10 second runtime we effectively throw away the last digit for each
thread records and it's even worse for larger runtime. This kind of
naive summing can easily add up to quite large differencies.

E.g. for a machine with 256 CPUs and 10 seconds the value would be on
average smaller by:

	512 (number of threads) * 5 (average last digit) / 10 (runtime)

So on average the result printed would be smaller by 256 units.

Either we have to switch the records_per_sec to double and compute the
number in floating point, which should add up fine as long as the work
done by a threads is more or less the same.

Or use uint64_t as a fixed point and use one or two bits for a fraction,
which may be a bit safer than double and should work fine as long as
we round properly.

This should be easy to debug as well, just print the number computed by
the method that sum first and then divide and compare it with the number
that sums the already divided values. These two shouldn't differ much,
ideally the should be the same.

-- 
Cyril Hrubis
chrubis@suse.cz

-- 
Mailing list info: https://lists.linux.it/listinfo/ltp

Re: [LTP] [PATCH v2 2/2] ebizzy: prevent integer overflow in 64-bit systems

[Vishal Chourasia]

On 8/21/23 18:54, Cyril Hrubis wrote:
> Hi!
>> Signed-off-by: Vishal Chourasia <vishalc@linux.ibm.com>
>> Reviewed-by: Srikar Dronamraju <srikar@linux.vnet.ibm.com>
>> Reviewed-by: Shrikanth Hegde <sshegde@linux.vnet.ibm.com>
>> ---
>>  utils/benchmark/ebizzy-0.3/ebizzy.c | 7 +++----
>>  1 file changed, 3 insertions(+), 4 deletions(-)
>>
>> diff --git a/utils/benchmark/ebizzy-0.3/ebizzy.c b/utils/benchmark/ebizzy-0.3/ebizzy.c
>> index ae0981fbd..c3eac1133 100644
>> --- a/utils/benchmark/ebizzy-0.3/ebizzy.c
>> +++ b/utils/benchmark/ebizzy-0.3/ebizzy.c
>> @@ -456,7 +456,7 @@ static void start_threads(void)
>>  	unsigned int i;
>>  	struct rusage start_ru, end_ru;
>>  	struct timeval usr_time, sys_time;
>> -	uintptr_t records_read = 0;
>> +	uintptr_t records_per_sec = 0;
>>  	int err;
>>  
>>  	if (verbose)
>> @@ -493,14 +493,13 @@ static void start_threads(void)
>>  			fprintf(stderr, "Error joining thread %d\n", i);
>>  			exit(1);
>>  		}
>> -		records_read += record_thread;
>> +		records_per_sec += (record_thread / elapsed);
> 
> This actually introduces quite a bit rounding errors. Note that even
> with 10 second runtime we effectively throw away the last digit for each
> thread records and it's even worse for larger runtime. This kind of
> naive summing can easily add up to quite large differencies.
> 
> E.g. for a machine with 256 CPUs and 10 seconds the value would be on
> average smaller by:
> 
> 	512 (number of threads) * 5 (average last digit) / 10 (runtime)
> 
> So on average the result printed would be smaller by 256 units.
> 
> Either we have to switch the records_per_sec to double and compute the
> number in floating point, which should add up fine as long as the work
> done by a threads is more or less the same.
> 
> Or use uint64_t as a fixed point and use one or two bits for a fraction,
> which may be a bit safer than double and should work fine as long as
> we round properly.
> 
> This should be easy to debug as well, just print the number computed by
> the method that sum first and then divide and compare it with the number
> that sums the already divided values. These two shouldn't differ much,
> ideally the should be the same.
> Sorry for the late reply.

Thank you for your insights on the potential rounding errors. I do see
significant rounding off error with proposed implementation.

$ ./ebizzy -S 10 -t 512
Method 1: 3049243 records/s
Method 2: 3049014 records/s
real 10.00 s
user 943.82 s
sys   0.00 s

$ ./ebizzy -S 10 -t 1000
Method 1: 2181487 records/s
Method 2: 2181041 records/s
real 10.00 s
user 947.33 s
sys   9.33 s

-- 
Mailing list info: https://lists.linux.it/listinfo/ltp

Re: [LTP] [PATCH v2 2/2] ebizzy: prevent integer overflow in 64-bit systems

[Vishal Chourasia]

On 8/21/23 18:54, Cyril Hrubis wrote:
> Hi!
>> Signed-off-by: Vishal Chourasia <vishalc@linux.ibm.com>
>> Reviewed-by: Srikar Dronamraju <srikar@linux.vnet.ibm.com>
>> Reviewed-by: Shrikanth Hegde <sshegde@linux.vnet.ibm.com>
>> ---
>>  utils/benchmark/ebizzy-0.3/ebizzy.c | 7 +++----
>>  1 file changed, 3 insertions(+), 4 deletions(-)
>>
>> diff --git a/utils/benchmark/ebizzy-0.3/ebizzy.c b/utils/benchmark/ebizzy-0.3/ebizzy.c
>> index ae0981fbd..c3eac1133 100644
>> --- a/utils/benchmark/ebizzy-0.3/ebizzy.c
>> +++ b/utils/benchmark/ebizzy-0.3/ebizzy.c
>> @@ -456,7 +456,7 @@ static void start_threads(void)
>>  	unsigned int i;
>>  	struct rusage start_ru, end_ru;
>>  	struct timeval usr_time, sys_time;
>> -	uintptr_t records_read = 0;
>> +	uintptr_t records_per_sec = 0;
>>  	int err;
>>  
>>  	if (verbose)
>> @@ -493,14 +493,13 @@ static void start_threads(void)
>>  			fprintf(stderr, "Error joining thread %d\n", i);
>>  			exit(1);
>>  		}
>> -		records_read += record_thread;
>> +		records_per_sec += (record_thread / elapsed);
> 
> This actually introduces quite a bit rounding errors. Note that even
> with 10 second runtime we effectively throw away the last digit for each
> thread records and it's even worse for larger runtime. This kind of
> naive summing can easily add up to quite large differencies.
> 
> E.g. for a machine with 256 CPUs and 10 seconds the value would be on
> average smaller by:
> 
> 	512 (number of threads) * 5 (average last digit) / 10 (runtime)
> 
> So on average the result printed would be smaller by 256 units.
> 
> Either we have to switch the records_per_sec to double and compute the
> number in floating point, which should add up fine as long as the work
> done by a threads is more or less the same.
> 
> Or use uint64_t as a fixed point and use one or two bits for a fraction,
> which may be a bit safer than double and should work fine as long as
> we round properly.
> 
> This should be easy to debug as well, just print the number computed by
> the method that sum first and then divide and compare it with the number
> that sums the already divided values. These two shouldn't differ much,
> ideally the should be the same.
> 
To address this, We can modify the code to keep the records per second
as a `double` type until the point of printing. This ensures that we
maintain precision throughout the calculation.

diff --git a/utils/benchmark/ebizzy-0.3/ebizzy.c
b/utils/benchmark/ebizzy-0.3/ebizzy.c
index ffc439a24..f9bc41ba9 100644
--- a/utils/benchmark/ebizzy-0.3/ebizzy.c
+++ b/utils/benchmark/ebizzy-0.3/ebizzy.c
@@ -456,6 +456,7 @@ static void start_threads(void)
        unsigned int i;
        struct rusage start_ru, end_ru;
        struct timeval usr_time, sys_time;
+       uintptr_t records = 0;
        double records_per_sec = 0.0;
        int err;

@@ -493,13 +494,15 @@ static void start_threads(void)
                        fprintf(stderr, "Error joining thread %d\n", i);
                        exit(1);
                }
+               records += record_thread;
                records_per_sec += ((double)record_thread / elapsed);
        }

        if (verbose)
                printf("Threads finished\n");

-       printf("%tu records/s\n", (uintptr_t) records_per_sec);
+       printf("Method 1: %tu records/s\n", (uintptr_t)((double)records
/ elapsed));
+       printf("Method 2: %tu records/s\n", (uintptr_t) records_per_sec);

        usr_time = difftimeval(&end_ru.ru_utime, &start_ru.ru_utime);
        sys_time = difftimeval(&end_ru.ru_stime, &start_ru.ru_stime);

Both methods yield the same result, confirming the accuracy of the
calculation. Here are some sample outputs:


$ ./ebizzy -S 10 -t 512
Method 1: 3049076 records/s
Method 2: 3049076 records/s

$ ./ebizzy -S 10 -t 1000
Method 1: 2273819 records/s
Method 2: 2273819 records/s

I will be sending a proper patch as reply to this thread.

vishal.c

-- 
Mailing list info: https://lists.linux.it/listinfo/ltp

[LTP] [PATCH v3] ebizzy: prevent integer overflow in 64-bit systems

[Vishal Chourasia]

By handling the rate computation within the thread joining loop, we've optimized
our storage, ensuring we don't risk integer overflow, particularly in 64-bit
systems. Given that `uintptr_t` can handle values up to `(2^64)-1`, to create an
overflow with the current implementation on a system with 9,000,000,000
records/sec values, one would need to run more than (2^64-1)/9 billion threads,
which is astronomically high and practically impossible.

This change reinforces the reliability of our code on high-performance, 64-bit
systems, ensuring accurate record counting without potential overflows.

In the `start_threads` function of the `ebizzy` benchmark utility, the variable
previously named `records_read` has been refactored to `records_per_sec` to more
accurately reflect its purpose, which is to store the rate of records per
second.

Reviewed-by: Shrikanth Hegde <sshegde@linux.vnet.ibm.com>
Reviewed-by: Srikar Dronamraju <srikar@linux.vnet.ibm.com>
Signed-off-by: Vishal Chourasia <vishalc@linux.ibm.com>

---
 utils/benchmark/ebizzy-0.3/ebizzy.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/utils/benchmark/ebizzy-0.3/ebizzy.c b/utils/benchmark/ebizzy-0.3/ebizzy.c
index ae0981fbd..ffc439a24 100644
--- a/utils/benchmark/ebizzy-0.3/ebizzy.c
+++ b/utils/benchmark/ebizzy-0.3/ebizzy.c
@@ -456,7 +456,7 @@ static void start_threads(void)
 	unsigned int i;
 	struct rusage start_ru, end_ru;
 	struct timeval usr_time, sys_time;
-	uintptr_t records_read = 0;
+	double records_per_sec = 0.0; 
 	int err;
 
 	if (verbose)
@@ -493,14 +493,13 @@ static void start_threads(void)
 			fprintf(stderr, "Error joining thread %d\n", i);
 			exit(1);
 		}
-		records_read += record_thread;
+		records_per_sec += ((double)record_thread / elapsed);
 	}
 
 	if (verbose)
 		printf("Threads finished\n");
 
-	printf("%tu records/s\n",
-	       (uintptr_t)(((double)records_read) / elapsed));
+	printf("%tu records/s\n", (uintptr_t) records_per_sec); 
 
 	usr_time = difftimeval(&end_ru.ru_utime, &start_ru.ru_utime);
 	sys_time = difftimeval(&end_ru.ru_stime, &start_ru.ru_stime);
-- 
2.39.3


-- 
Mailing list info: https://lists.linux.it/listinfo/ltp

Re: [LTP] [PATCH v3] ebizzy: prevent integer overflow in 64-bit systems

[Cyril Hrubis]

Hi!
Reviewed-by: Cyril Hrubis <chrubis@suse.cz>

-- 
Cyril Hrubis
chrubis@suse.cz

-- 
Mailing list info: https://lists.linux.it/listinfo/ltp

Re: [LTP] [PATCH v3] ebizzy: prevent integer overflow in 64-bit systems

[Richard Palethorpe]

hello,

Merged!

Cyril Hrubis <chrubis@suse.cz> writes:

> Hi!
> Reviewed-by: Cyril Hrubis <chrubis@suse.cz>
>
> -- 
> Cyril Hrubis
> chrubis@suse.cz


-- 
Thank you,
Richard.

-- 
Mailing list info: https://lists.linux.it/listinfo/ltp