svn commit: r313321 - stable/10/usr.bin/sort

[Pedro F. Giffuni]

Author: pfg
Date: Mon Feb  6 05:27:05 2017
New Revision: 313321
URL: https://svnweb.freebsd.org/changeset/base/313321

Log:
  MFC r312667:
  sort - Don't live-loop threads.
  
  Worker threads now use a pthread_cond_t to wait for work instead of
  burning the cpu up.
  
  Obtained from:	DragonflyBSD (07774aea0ccf64a48fcfad8899e3bf7c8f18277a)

Modified:
  stable/10/usr.bin/sort/radixsort.c
Directory Properties:
  stable/10/   (props changed)

Modified: stable/10/usr.bin/sort/radixsort.c
==============================================================================
--- stable/10/usr.bin/sort/radixsort.c	Mon Feb  6 05:24:17 2017	(r313320)
+++ stable/10/usr.bin/sort/radixsort.c	Mon Feb  6 05:27:05 2017	(r313321)
@@ -83,12 +83,12 @@ static struct level_stack *g_ls;
 
 #if defined(SORT_THREADS)
 /* stack guarding mutex */
+static pthread_cond_t g_ls_cond;
 static pthread_mutex_t g_ls_mutex;
 
 /* counter: how many items are left */
 static size_t sort_left;
 /* guarding mutex */
-static pthread_mutex_t sort_left_mutex;
 
 /* semaphore to count threads */
 static sem_t mtsem;
@@ -99,23 +99,25 @@ static sem_t mtsem;
 static inline void
 sort_left_dec(size_t n)
 {
-
-	pthread_mutex_lock(&sort_left_mutex);
+	pthread_mutex_lock(&g_ls_mutex);
 	sort_left -= n;
-	pthread_mutex_unlock(&sort_left_mutex);
+	if (sort_left == 0 && nthreads > 1)
+		pthread_cond_broadcast(&g_ls_cond);
+	pthread_mutex_unlock(&g_ls_mutex);
 }
 
 /*
  * Do we have something to sort ?
+ *
+ * This routine does not need to be locked.
  */
 static inline bool
 have_sort_left(void)
 {
 	bool ret;
 
-	pthread_mutex_lock(&sort_left_mutex);
 	ret = (sort_left > 0);
-	pthread_mutex_unlock(&sort_left_mutex);
+
 	return (ret);
 }
 
@@ -146,6 +148,11 @@ push_ls(struct sort_level* sl)
 
 #if defined(SORT_THREADS)
 	if (nthreads > 1)
+		pthread_cond_signal(&g_ls_cond);
+#endif
+
+#if defined(SORT_THREADS)
+	if (nthreads > 1)
 		pthread_mutex_unlock(&g_ls_mutex);
 #endif
 }
@@ -184,13 +191,19 @@ pop_ls_mt(void)
 
 	pthread_mutex_lock(&g_ls_mutex);
 
-	if (g_ls) {
-		sl = g_ls->sl;
-		saved_ls = g_ls;
-		g_ls = g_ls->next;
-	} else {
+	for (;;) {
+		if (g_ls) {
+			sl = g_ls->sl;
+			saved_ls = g_ls;
+			g_ls = g_ls->next;
+			break;
+		}
 		sl = NULL;
 		saved_ls = NULL;
+
+		if (have_sort_left() == 0)
+			break;
+		pthread_cond_wait(&g_ls_cond, &g_ls_mutex);
 	}
 
 	pthread_mutex_unlock(&g_ls_mutex);
@@ -493,13 +506,8 @@ run_sort_cycle_mt(void)
 
 	for (;;) {
 		slc = pop_ls_mt();
-		if (slc == NULL) {
-			if (have_sort_left()) {
-				pthread_yield();
-				continue;
-			}
+		if (slc == NULL)
 			break;
-		}
 		run_sort_level_next(slc);
 	}
 }
@@ -510,9 +518,7 @@ run_sort_cycle_mt(void)
 static void*
 sort_thread(void* arg)
 {
-
 	run_sort_cycle_mt();
-
 	sem_post(&mtsem);
 
 	return (arg);
@@ -608,8 +614,7 @@ run_top_sort_level(struct sort_level *sl
 			pthread_t pth;
 
 			pthread_attr_init(&attr);
-			pthread_attr_setdetachstate(&attr,
-			    PTHREAD_DETACHED);
+			pthread_attr_setdetachstate(&attr, PTHREAD_DETACHED);
 
 			for (;;) {
 				int res = pthread_create(&pth, &attr,
@@ -626,7 +631,7 @@ run_top_sort_level(struct sort_level *sl
 			pthread_attr_destroy(&attr);
 		}
 
-		for(i = 0; i < nthreads; ++i)
+		for (i = 0; i < nthreads; ++i)
 			sem_wait(&mtsem);
 	}
 #endif /* defined(SORT_THREADS) */
@@ -649,7 +654,7 @@ run_sort(struct sort_list_item **base, s
 		pthread_mutexattr_settype(&mattr, PTHREAD_MUTEX_ADAPTIVE_NP);
 
 		pthread_mutex_init(&g_ls_mutex, &mattr);
-		pthread_mutex_init(&sort_left_mutex, &mattr);
+		pthread_cond_init(&g_ls_cond, NULL);
 
 		pthread_mutexattr_destroy(&mattr);
 
@@ -677,7 +682,6 @@ run_sort(struct sort_list_item **base, s
 	if (nthreads > 1) {
 		sem_destroy(&mtsem);
 		pthread_mutex_destroy(&g_ls_mutex);
-		pthread_mutex_destroy(&sort_left_mutex);
 	}
 	nthreads = nthreads_save;
 #endif