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