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
99 typedef 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 */
107 int parse_measure(mes_t * measures);
108
109 sem_t *sem_synchro;
110 sem_t *sem_ending;
111
main(int argc,char * argv[])112 int 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
407 struct 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
parse_measure(mes_t * measures)418 int 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