1/*
2 * Copyright (c) 2004, Bull S.A..  All rights reserved.
3 * Created by: Sebastien Decugis
4
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms of version 2 of the GNU General Public License as
7 * published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it would be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12 *
13 * You should have received a copy of the GNU General Public License along
14 * with this program; if not, write the Free Software Foundation, Inc., 59
15 * Temple Place - Suite 330, Boston MA 02111-1307, USA.
16
17
18 * This scalability sample aims to test the following assertions:
19 *  -> If pthread_create fails because of a lack of a resource, or
20 	PTHREAD_THREADS_MAX threads already exist, EAGAIN shall be returned.
21 *  -> It also tests that the thread creation time does not depend on the # of threads
22 *     already created.
23
24 * The steps are:
25 * -> Create threads until failure
26
27 */
28
29
30 /* We are testing conformance to IEEE Std 1003.1, 2003 Edition */
31 #define _POSIX_C_SOURCE 200112L
32
33 /* Some routines are part of the XSI Extensions */
34#ifndef WITHOUT_XOPEN
35 #define _XOPEN_SOURCE	600
36#endif
37/********************************************************************************************/
38/****************************** standard includes *****************************************/
39/********************************************************************************************/
40 #include <pthread.h>
41 #include <stdarg.h>
42 #include <stdio.h>
43 #include <stdlib.h>
44 #include <string.h>
45 #include <unistd.h>
46
47 #include <sched.h>
48 #include <semaphore.h>
49 #include <errno.h>
50 #include <assert.h>
51 #include <sys/wait.h>
52 #include <math.h>
53
54
55/********************************************************************************************/
56/******************************   Test framework   *****************************************/
57/********************************************************************************************/
58 #include "testfrmw.h"
59 #include "testfrmw.c"
60 /* This header is responsible for defining the following macros:
61  * UNRESOLVED(ret, descr);
62  *    where descr is a description of the error and ret is an int (error code for example)
63  * FAILED(descr);
64  *    where descr is a short text saying why the test has failed.
65  * PASSED();
66  *    No parameter.
67  *
68  * Both three macros shall terminate the calling process.
69  * The testcase shall not terminate in any other maneer.
70  *
71  * The other file defines the functions
72  * void output_init()
73  * void output(char * string, ...)
74  *
75  * Those may be used to output information.
76  */
77
78/********************************************************************************************/
79/********************************** Configuration ******************************************/
80/********************************************************************************************/
81#ifndef SCALABILITY_FACTOR
82#define SCALABILITY_FACTOR 1
83#endif
84#ifndef VERBOSE
85#define VERBOSE 1
86#endif
87
88#define RESOLUTION (5 * SCALABILITY_FACTOR)
89
90#ifdef PLOT_OUTPUT
91#undef VERBOSE
92#define VERBOSE 0
93#endif
94
95/********************************************************************************************/
96/***********************************    Test cases  *****************************************/
97/********************************************************************************************/
98
99#include "threads_scenarii.c"
100
101/* This file will define the following objects:
102 * scenarii: array of struct __scenario type.
103 * NSCENAR : macro giving the total # of scenarii
104 * scenar_init(): function to call before use the scenarii array.
105 * scenar_fini(): function to call after end of use of the scenarii array.
106 */
107
108
109/********************************************************************************************/
110/***********************************    Real Test   *****************************************/
111/********************************************************************************************/
112
113/* The next structure is used to save the tests measures */
114typedef struct __mes_t
115{
116	int  nthreads;
117	long _data[ NSCENAR ]; /* As we store µsec values, a long type should be amply enough. */
118	struct __mes_t *next;
119} mes_t;
120
121/* Forward declaration */
122int parse_measure(mes_t * measures);
123
124
125
126pthread_mutex_t m_synchro=PTHREAD_MUTEX_INITIALIZER;
127
128void * threaded(void * arg)
129{
130	int ret=0;
131
132	/* Signal we're done */
133	do { ret = sem_post(&scenarii[sc].sem); }
134	while ((ret == -1) && (errno == EINTR));
135	if (ret == -1)  {  UNRESOLVED(errno, "Failed to wait for the semaphore");  }
136
137	/* Wait for all threads being created */
138	ret = pthread_mutex_lock(&m_synchro);
139	if (ret != 0)  {  UNRESOLVED(ret, "Mutex lock failed");  }
140	(*(int *)arg) += 1;
141	ret = pthread_mutex_unlock(&m_synchro);
142	if (ret != 0)  {  UNRESOLVED(ret, "Mutex unlock failed");  }
143
144	return arg;
145}
146
147int main (int argc, char *argv[])
148{
149	int ret=0;
150	pthread_t child;
151	pthread_t *th;
152
153	int nthreads, ctl, i, tmp;
154
155	struct timespec ts_ref, ts_fin;
156
157	mes_t sentinel;
158	mes_t *m_cur, *m_tmp;
159
160	long PTHREAD_THREADS_MAX = sysconf(_SC_THREAD_THREADS_MAX);
161	long my_max = 1000 * SCALABILITY_FACTOR ;
162
163	/* Initialize the measure list */
164	m_cur = &sentinel;
165	m_cur->next = NULL;
166
167	/* Initialize output routine */
168	output_init();
169
170	if (PTHREAD_THREADS_MAX > 0)
171		my_max = PTHREAD_THREADS_MAX;
172
173	th = (pthread_t *)calloc(1 + my_max, sizeof(pthread_t));
174	if (th == NULL)  {  UNRESOLVED(errno, "Not enough memory for thread storage");  }
175
176	/* Initialize thread attribute objects */
177	scenar_init();
178
179	#ifdef PLOT_OUTPUT
180	printf("# COLUMNS %d #threads", NSCENAR + 1);
181	for (sc=0; sc<NSCENAR; sc++)
182		printf(" %i", sc);
183	printf("\n");
184	#endif
185
186	for (sc=0; sc < NSCENAR; sc++)
187	{
188		if (scenarii[sc].bottom == NULL) /* skip the alternate stacks as we could create only 1 */
189		{
190			#if VERBOSE > 0
191			output("-----\n");
192			output("Starting test with scenario (%i): %s\n", sc, scenarii[sc].descr);
193			#endif
194
195			/* Block every (about to be) created threads */
196			ret = pthread_mutex_lock(&m_synchro);
197			if (ret != 0)  {  UNRESOLVED(ret, "Mutex lock failed");  }
198
199			ctl=0;
200			nthreads=0;
201			m_cur = &sentinel;
202
203			/* Create 1 thread for testing purpose */
204			ret = pthread_create(&child, &scenarii[sc].ta, threaded, &ctl);
205			switch (scenarii[sc].result)
206			{
207				case 0: /* Operation was expected to succeed */
208					if (ret != 0)  {  UNRESOLVED(ret, "Failed to create this thread");  }
209					break;
210
211				case 1: /* Operation was expected to fail */
212					if (ret == 0)  {  UNRESOLVED(-1, "An error was expected but the thread creation succeeded");  }
213					break;
214
215				case 2: /* We did not know the expected result */
216				default:
217					#if VERBOSE > 0
218					if (ret == 0)
219						{ output("Thread has been created successfully for this scenario\n"); }
220					else
221						{ output("Thread creation failed with the error: %s\n", strerror(ret)); }
222					#endif
223					;
224			}
225			if (ret == 0) /* The new thread is running */
226			{
227
228				while (1) /* we will break */
229				{
230					/* read clock */
231					ret = clock_gettime(CLOCK_REALTIME, &ts_ref);
232					if (ret != 0)  {  UNRESOLVED(errno, "Unable to read clock");  }
233
234					/* create a new thread */
235					ret = pthread_create(&th[nthreads], &scenarii[sc].ta, threaded, &ctl);
236
237					/* stop here if we've got EAGAIN */
238					if (ret == EAGAIN)
239						break;
240
241// temporary hack
242if (ret == ENOMEM)  break;
243					nthreads++;
244
245					/* FAILED if error is != EAGAIN or nthreads > PTHREAD_THREADS_MAX */
246					if (ret != 0)
247					{
248						output("pthread_create returned: %i (%s)\n", ret, strerror(ret));
249						FAILED("pthread_create did not return EAGAIN on a lack of resource");
250					}
251					if (nthreads > my_max)
252					{
253						if (PTHREAD_THREADS_MAX > 0)
254						{
255							FAILED("We were able to create more than PTHREAD_THREADS_MAX threads");
256						}
257						else
258						{
259							break;
260						}
261					}
262
263					/* wait for the semaphore */
264					do { ret = sem_wait(&scenarii[sc].sem); }
265					while ((ret == -1) && (errno == EINTR));
266					if (ret == -1)  {  UNRESOLVED(errno, "Failed to wait for the semaphore");  }
267
268					/* read clock */
269					ret = clock_gettime(CLOCK_REALTIME, &ts_fin);
270					if (ret != 0)  {  UNRESOLVED(errno, "Unable to read clock");  }
271
272					/* add to the measure list if nthreads % resolution == 0 */
273					if ((nthreads % RESOLUTION) == 0)
274					{
275						if (m_cur->next == NULL)
276						{
277							/* Create an empty new element */
278							m_tmp = (mes_t *) malloc(sizeof(mes_t));
279							if (m_tmp == NULL) { UNRESOLVED(errno, "Unable to alloc memory for measure saving");  }
280							m_tmp->nthreads = nthreads;
281							m_tmp->next = NULL;
282							for (tmp=0; tmp<NSCENAR; tmp++)
283								m_tmp->_data[tmp]= 0;
284							m_cur->next = m_tmp;
285						}
286
287						/* Add this measure to the next element */
288						m_cur = m_cur->next;
289						m_cur->_data[sc] = ((ts_fin.tv_sec - ts_ref.tv_sec) * 1000000) + ((ts_fin.tv_nsec - ts_ref.tv_nsec) / 1000) ;
290
291						#if VERBOSE > 5
292						output("Added the following measure: sc=%i, n=%i, v=%li\n", sc, nthreads, m_cur->_data[sc]);
293						#endif
294					}
295				}
296				#if VERBOSE > 3
297				output("Could not create anymore thread. Current count is %i\n", nthreads);
298				#endif
299
300				/* Unblock every created threads */
301				ret = pthread_mutex_unlock(&m_synchro);
302				if (ret != 0)  {  UNRESOLVED(ret, "Mutex unlock failed");  }
303
304				if (scenarii[sc].detached == 0)
305				{
306					#if VERBOSE > 3
307					output("Joining the threads\n");
308					#endif
309					for (i = 0; i < nthreads; i++)
310					{
311						ret = pthread_join(th[i], NULL);
312						if (ret != 0)  {  UNRESOLVED(ret, "Unable to join a thread");  }
313					}
314
315					ret = pthread_join(child, NULL);
316					if (ret != 0)  {  UNRESOLVED(ret, "Unalbe to join a thread");  }
317
318				}
319				#if VERBOSE > 3
320				output("Waiting for threads (almost) termination\n");
321				#endif
322				do {
323					ret = pthread_mutex_lock(&m_synchro);
324					if (ret != 0)  {  UNRESOLVED(ret, "Mutex lock failed");  }
325
326					tmp = ctl;
327
328					ret = pthread_mutex_unlock(&m_synchro);
329					if (ret != 0)  {  UNRESOLVED(ret, "Mutex unlock failed");  }
330				} while (tmp != nthreads + 1);
331
332			} /* The thread was created */
333
334	}	} /* next scenario */
335
336	/* Free some memory before result parsing */
337	free(th);
338
339	/* Compute the results */
340	ret = parse_measure(&sentinel);
341
342
343	/* Free the resources and output the results */
344
345	#if VERBOSE > 5
346	printf("Dump : \n");
347	printf("%8.8s", "nth");
348	for (i = 0; i<NSCENAR; i++)
349		printf("|   %2.2i   ", i);
350	printf("\n");
351	#endif
352	while (sentinel.next != NULL)
353	{
354		m_cur = sentinel.next;
355		#if (VERBOSE > 5) || defined(PLOT_OUTPUT)
356		printf("%8.8i", m_cur->nthreads);
357		for (i=0; i<NSCENAR; i++)
358			printf(" %1.1li.%6.6li", m_cur->_data[i] / 1000000, m_cur->_data[i] % 1000000);
359		printf("\n");
360		#endif
361		sentinel.next = m_cur->next;
362		free(m_cur);
363	}
364
365	scenar_fini();
366
367	#if VERBOSE > 0
368	output("-----\n");
369	output("All test data destroyed\n");
370	output("Test PASSED\n");
371	#endif
372
373	PASSED;
374}
375
376
377
378
379
380/***
381 * The next function will seek for the better model for each series of measurements.
382 *
383 * The tested models are: -- X = # threads; Y = latency
384 * -> Y = a;      -- Error is r1 = avg( (Y - Yavg)² );
385 * -> Y = aX + b; -- Error is r2 = avg( (Y -aX -b)² );
386 *                -- where a = avg ( (X - Xavg)(Y - Yavg) ) / avg( ( X - Xavg)² )
387 *                --         Note: We will call _q = sum( (X - Xavg) * (Y - Yavg) );
388 *                --                       and  _d = sum( (X - Xavg)² );
389 *                -- and   b = Yavg - a * Xavg
390 * -> Y = c * X^a;-- Same as previous, but with log(Y) = a log(X) + b; and b = log(c). Error is r3
391 * -> Y = exp(aX + b); -- log(Y) = aX + b. Error is r4
392 *
393 * We compute each error factor (r1, r2, r3, r4) then search which is the smallest (with ponderation).
394 * The function returns 0 when r1 is the best for all cases (latency is constant) and !0 otherwise.
395 */
396
397struct row
398{
399	long X;  /* the X values -- copied from function argument */
400	long Y[NSCENAR];  /* the Y values -- copied from function argument */
401	long _x[NSCENAR]; /* Value X - Xavg */
402	long _y[NSCENAR]; /* Value Y - Yavg */
403	double LnX; /* Natural logarithm of X values */
404	double LnY[NSCENAR]; /* Natural logarithm of Y values */
405	double _lnx[NSCENAR]; /* Value LnX - LnXavg */
406	double _lny[NSCENAR]; /* Value LnY - LnYavg */
407};
408
409int parse_measure(mes_t * measures)
410{
411	int ret, i, r;
412
413	mes_t *cur;
414
415	double Xavg[NSCENAR], Yavg[NSCENAR];
416	double LnXavg[NSCENAR], LnYavg[NSCENAR];
417
418	int N;
419
420	double r1[NSCENAR], r2[NSCENAR], r3[NSCENAR], r4[NSCENAR];
421
422	/* Some more intermediate vars */
423	long double _q[3][NSCENAR];
424	long double _d[3][NSCENAR];
425
426	long double t; /* temp value */
427
428	struct row *Table = NULL;
429
430	/* This array contains the last element of each serie */
431	int array_max[NSCENAR];
432
433	/* Initialize the datas */
434	for (i=0; i<NSCENAR; i++)
435	{
436		array_max[i] = -1; /* means no data */
437		Xavg[i] = 0.0;
438		LnXavg[i] = 0.0;
439		Yavg[i] = 0.0;
440		LnYavg[i] = 0.0;
441		r1[i] = 0.0;
442		r2[i] = 0.0;
443		r3[i] = 0.0;
444		r4[i] = 0.0;
445		_q[0][i]=0.0;
446		_q[1][i]=0.0;
447		_q[2][i]=0.0;
448		_d[0][i]=0.0;
449		_d[1][i]=0.0;
450		_d[2][i]=0.0;
451	}
452	N=0;
453	cur = measures;
454
455	#if VERBOSE > 1
456	output("Data analysis starting\n");
457	#endif
458
459	/* We start with reading the list to find:
460	 * -> number of elements, to assign an array.
461	 * -> average values
462	 */
463	while (cur->next != NULL)
464	{
465		cur = cur->next;
466
467		N++;
468
469		for (i=0; i<NSCENAR; i++)
470		{
471			if (cur->_data[i] != 0)
472			{
473				array_max[i]=N;
474				Xavg[i] += (double) cur->nthreads;
475				LnXavg[i] += log( (double) cur->nthreads);
476				Yavg[i] += (double) cur->_data[i];
477				LnYavg[i] += log( (double) cur->_data[i] );
478			}
479		}
480	}
481
482	/* We have the sum; we can divide to obtain the average values */
483	for (i=0; i<NSCENAR; i++)
484	{
485		if (array_max[i] != -1)
486		{
487			Xavg[i] /= array_max[i];
488			LnXavg[i] /= array_max[i];
489			Yavg[i] /= array_max[i];
490			LnYavg[i] /= array_max[i];
491		}
492	}
493
494	#if VERBOSE > 1
495	output(" Found %d rows and %d columns\n", N, NSCENAR);
496	#endif
497
498
499	/* We will now alloc the array ... */
500	Table = calloc(N, sizeof( struct row ));
501	if (Table == NULL)  {  UNRESOLVED(errno, "Unable to alloc space for results parsing");  }
502
503	/* ... and fill it */
504	N = 0;
505	cur = measures;
506
507	while (cur->next != NULL)
508	{
509		cur = cur->next;
510
511		Table[N].X = (long) cur->nthreads;
512		Table[N].LnX = log((double) cur->nthreads);
513		for (i=0; i<NSCENAR; i++)
514		{
515			if (array_max[i] > N)
516			{
517				Table[N]._x[i] = Table[N].X - Xavg[i] ;
518				Table[N]._lnx[i] = Table[N].LnX - LnXavg[i];
519				Table[N].Y[i] = cur->_data[i];
520				Table[N]._y[i] = Table[N].Y[i] - Yavg[i] ;
521				Table[N].LnY[i] = log((double) cur->_data[i]);
522				Table[N]._lny[i] = Table[N].LnY[i] - LnYavg[i];
523			}
524		}
525
526		N++;
527	}
528
529	/* We won't need the list anymore -- we'll work with the array which should be faster. */
530	#if VERBOSE > 1
531	output(" Data was stored in an array.\n");
532	#endif
533
534	/* We need to read the full array at least twice to compute all the error factors */
535
536	/* In the first pass, we'll compute:
537	 * -> r1 for each scenar.
538	 * -> "a" factor for linear (0), power (1) and exponential (2) approximations -- with using the _d and _q vars.
539	 */
540	#if VERBOSE > 1
541	output("Starting first pass...\n");
542	#endif
543	for (i=0; i<NSCENAR; i++)
544	{
545		for (r=0; r<array_max[i]; r++)
546		{
547			r1[i] += ((double)Table[r]._y[i] / array_max[i]) * (double)Table[r]._y[i];
548
549			_q[0][i] += Table[r]._y[i] * Table[r]._x[i];
550			_d[0][i] += Table[r]._x[i] * Table[r]._x[i];
551
552			_q[1][i] += Table[r]._lny[i] * Table[r]._lnx[i];
553			_d[1][i] += Table[r]._lnx[i] * Table[r]._lnx[i];
554
555			_q[2][i] += Table[r]._lny[i] * Table[r]._x[i];
556			_d[2][i] += Table[r]._x[i] * Table[r]._x[i];
557		}
558	}
559
560	/* First pass is terminated; a2 = _q[0]/_d[0]; a3 = _q[1]/_d[1]; a4 = _q[2]/_d[2] */
561
562	/* In the first pass, we'll compute:
563	 * -> r2, r3, r4 for each scenar.
564	 */
565
566	#if VERBOSE > 1
567	output("Starting second pass...\n");
568	#endif
569	for (i=0; i<NSCENAR; i++)
570	{
571		for (r=0; r<array_max[i]; r++)
572		{
573			/* r2 = avg((y - ax -b)²);  t = (y - ax - b) = (y - yavg) - a (x - xavg); */
574			t = ( Table[r]._y[i] - ((_q[0][i] * Table[r]._x[i]) / _d[0][i]));
575			r2[i] += t * t / array_max[i]  ;
576
577			/* r3 = avg(( y - c.x^a) ²);
578			    t = y - c * x ^ a
579			      = y - log (LnYavg - (_q[1]/_d[1]) * LnXavg) * x ^ (_q[1]/_d[1])
580			*/
581			t = (   Table[r].Y[i]
582			      - ( logl ( LnYavg[i] - (_q[1][i] / _d[1][i] ) * LnXavg[i])
583			        * powl( Table[r].X,  (_q[1][i] / _d[1][i] ))
584			    )   );
585			r3[i] += t * t / array_max[i] ;
586
587			/* r4 = avg(( y - exp(ax+b))²);
588			    t = y - exp(ax+b)
589			      = y - exp( _q[2]/_d[2] * x + ( LnYavg - (_q[2]/_d[2] * Xavg) ));
590			      = y - exp( _q[2]/_d[2] * (x - Xavg) + LnYavg );
591			*/
592			t = (   Table[r].Y[i]
593			      - expl( ( _q[2][i] / _d[2][i] ) * Table[r]._x[i] + LnYavg[i] ) );
594			r4[i] += t * t / array_max[i] ;
595
596		}
597	}
598
599	#if VERBOSE > 1
600	output("All computing terminated.\n");
601	#endif
602	ret = 0;
603	for (i=0; i<NSCENAR; i++)
604	{
605		#if VERBOSE > 1
606		output("\nScenario: %s\n", scenarii[i].descr);
607
608		output(" # of data: %i\n", array_max[i]);
609
610		output("  Model: Y = k\n");
611		output("       k = %g\n", Yavg[i]);
612		output("    Divergence %g\n", r1[i]);
613
614		output("  Model: Y = a * X + b\n");
615		output("       a = %Lg\n", _q[0][i] / _d[0][i]);
616		output("       b = %Lg\n", Yavg[i] - ((_q[0][i] / _d[0][i]) * Xavg[i]));
617		output("    Divergence %g\n", r2[i]);
618
619		output("  Model: Y = c * X ^ a\n");
620		output("       a = %Lg\n", _q[1][i] / _d[1][i]);
621		output("       c = %Lg\n", logl ( LnYavg[i] - (_q[1][i] / _d[1][i] ) * LnXavg[i]));
622		output("    Divergence %g\n", r2[i]);
623
624		output("  Model: Y = exp(a * X + b)\n");
625		output("       a = %Lg\n", _q[2][i] / _d[2][i]);
626		output("       b = %Lg\n", LnYavg[i] - ((_q[2][i] / _d[2][i]) * Xavg[i]));
627		output("    Divergence %g\n", r2[i]);
628		#endif
629
630		if (array_max[i] != -1)
631		{
632			/* Compare r1 to other values, with some ponderations */
633			if ((r1[i] > 1.1 * r2[i]) || (r1[i] > 1.2 * r3[i]) || (r1[i] > 1.3 * r4[i]))
634					ret++;
635			#if VERBOSE > 1
636			else
637				output(" Sanction: OK\n");
638			#endif
639		}
640	}
641
642	/* We need to free the array */
643	free(Table);
644
645	/* We're done */
646	return ret;
647}
648
649