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