Skip to contentSkip to conversation

Fix Integer Overflow and Thread Safety in Record Counting

PATCH In review Vishal Chourasia 3 participants 10 messages Aug 15, 2023 – Sep 7, 2023

lore
Share & tools
lore
#0 lore raw

v2 cover Fix Integer Overflow and Thread Safety in Record Counting

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/[email protected]/

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(-)
Signature · 5 lines
2.39.3


-- 
Mailing list info: https://lists.linux.it/listinfo/ltp
#1 lore raw

PATCH v2 1/2 Enhance Thread Safety in Record Counting

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.

---
 utils/benchmark/ebizzy-0.3/ebizzy.c | 21 +++++++++++++--------
 1 file changed, 13 insertions(+), 8 deletions(-)
utils/benchmark/ebizzy-0.3/ebizzy.c +13 -8
index 54b047130..ae0981fbd 100644
@@ -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);
Signature · 5 lines
2.39.3


-- 
Mailing list info: https://lists.linux.it/listinfo/ltp
#2 lore raw

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

Hi!
Applied, thanks.

Signature · 5 lines
Cyril Hrubis
[email protected]

-- 
Mailing list info: https://lists.linux.it/listinfo/ltp
#3 lore raw

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

In reply to 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.

---
 utils/benchmark/ebizzy-0.3/ebizzy.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)
utils/benchmark/ebizzy-0.3/ebizzy.c +3 -4
index ae0981fbd..c3eac1133 100644
@@ -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);
Signature · 5 lines
2.39.3


-- 
Mailing list info: https://lists.linux.it/listinfo/ltp
#4 lore raw

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

Hi!

Quoted 21 lines
---
 utils/benchmark/ebizzy-0.3/ebizzy.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)
utils/benchmark/ebizzy-0.3/ebizzy.c +1 -1
index ae0981fbd..c3eac1133 100644
@@ -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)

utils/benchmark/ebizzy-0.3/ebizzy.c static void start_threads(void) · line 496

Quoted 5 lines
utils/benchmark/ebizzy-0.3/ebizzy.c +1 -1
@@ -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.

Signature · 5 lines
Cyril Hrubis
[email protected]

-- 
Mailing list info: https://lists.linux.it/listinfo/ltp
#5 lore raw

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

Quoted 48 lines · Cyril Hrubis

Hi!

Quoted 21 lines
---
 utils/benchmark/ebizzy-0.3/ebizzy.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)
utils/benchmark/ebizzy-0.3/ebizzy.c +1 -1
index ae0981fbd..c3eac1133 100644
@@ -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)

utils/benchmark/ebizzy-0.3/ebizzy.c static void start_threads(void) · line 496

Quoted 5 lines
utils/benchmark/ebizzy-0.3/ebizzy.c +1 -1
@@ -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.

Quoted 5 lines

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
Signature · 1 line
Mailing list info: https://lists.linux.it/listinfo/ltp
#6 lore raw

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

In reply to Cyril Hrubis
Quoted 44 lines · Cyril Hrubis

Hi!

Quoted 21 lines
---
 utils/benchmark/ebizzy-0.3/ebizzy.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)
utils/benchmark/ebizzy-0.3/ebizzy.c +1 -1
index ae0981fbd..c3eac1133 100644
@@ -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)

utils/benchmark/ebizzy-0.3/ebizzy.c static void start_threads(void) · line 496

Quoted 5 lines
utils/benchmark/ebizzy-0.3/ebizzy.c +1 -1
@@ -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.

Quoted 9 lines

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.

(quoted diff) +0 -0

b/utils/benchmark/ebizzy-0.3/ebizzy.c
index ffc439a24..f9bc41ba9 100644

utils/benchmark/ebizzy-0.3/ebizzy.c +3 -1
@@ -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

Signature · 1 line
Mailing list info: https://lists.linux.it/listinfo/ltp
#7 lore raw

PATCH v3 1/1 ebizzy: prevent integer overflow in 64-bit systems

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.

---
 utils/benchmark/ebizzy-0.3/ebizzy.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)
utils/benchmark/ebizzy-0.3/ebizzy.c +3 -4
index ae0981fbd..ffc439a24 100644
@@ -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);
Signature · 5 lines
2.39.3


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