1 /*
2 * Copyright (c) 2005, 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 sem_init() duration does not depend on the # of semaphores
19 * in the system
20
21 * The steps are:
22 * -> Init semaphores until failure
23
24 * The test fails if the sem_init duration tends to grow with the # of semaphores,
25 * or if the failure at last semaphore creation is unexpected.
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 <math.h>
39 #include <errno.h>
40 #include <time.h>
41 #include <semaphore.h>
42
43 /********************************************************************************************/
44 /****************************** Test framework *****************************************/
45 /********************************************************************************************/
46 #include "testfrmw.h"
47 #include "testfrmw.c"
48 /* This header is responsible for defining the following macros:
49 * UNRESOLVED(ret, descr);
50 * where descr is a description of the error and ret is an int (error code for example)
51 * FAILED(descr);
52 * where descr is a short text saying why the test has failed.
53 * PASSED();
54 * No parameter.
55 *
56 * Both three macros shall terminate the calling process.
57 * The testcase shall not terminate in any other maneer.
58 *
59 * The other file defines the functions
60 * void output_init()
61 * void output(char * string, ...)
62 *
63 * Those may be used to output information.
64 */
65
66 /********************************************************************************************/
67 /********************************** Configuration ******************************************/
68 /********************************************************************************************/
69 #ifndef SCALABILITY_FACTOR
70 #define SCALABILITY_FACTOR 1
71 #endif
72 #ifndef VERBOSE
73 #define VERBOSE 1
74 #endif
75
76 #define BLOCKSIZE (1000 * SCALABILITY_FACTOR)
77
78 #define NSEM_LIMIT (1000 * BLOCKSIZE)
79
80 #ifdef PLOT_OUTPUT
81 #undef VERBOSE
82 #define VERBOSE 0
83 #endif
84
85 /********************************************************************************************/
86 /*********************************** Test *****************************************/
87 /********************************************************************************************/
88
89 /* The next structure is used to save the tests measures */
90
91 typedef struct __mes_t {
92 int nsem;
93 long _data_open; /* As we store µsec values, a long type should be enough. */
94 long _data_close; /* As we store µsec values, a long type should be enough. */
95
96 struct __mes_t *next;
97
98 struct __mes_t *prev;
99 } mes_t;
100
101 /* Forward declaration */
102 int parse_measure(mes_t * measures);
103
104 /* Structure to store created semaphores */
105
106 typedef struct __test_t {
107 sem_t sems[BLOCKSIZE];
108
109 struct __test_t *next;
110
111 struct __test_t *prev;
112 } test_t;
113
114 /* Test routine */
main(int argc,char * argv[])115 int main(int argc, char *argv[])
116 {
117 int ret, status, locerrno;
118 int nsem, i;
119
120 struct timespec ts_ref, ts_fin;
121 mes_t sentinel;
122 mes_t *m_cur, *m_tmp;
123
124 test_t sems;
125
126 struct __test_t *sems_cur = &sems, *sems_tmp;
127
128 long SEM_MAX = sysconf(_SC_SEM_NSEMS_MAX);
129
130 /* Initialize the measure list */
131 m_cur = &sentinel;
132 m_cur->next = NULL;
133 m_cur->prev = NULL;
134
135 /* Initialize output routine */
136 output_init();
137
138 /* Initialize sems */
139 sems_cur->next = NULL;
140 sems_cur->prev = NULL;
141
142 #if VERBOSE > 1
143 output("SEM_NSEMS_MAX: %ld\n", SEM_MAX);
144
145 #endif
146
147 #ifdef PLOT_OUTPUT
148 output("# COLUMNS 3 Semaphores sem_init sem_destroy\n");
149
150 #endif
151
152 nsem = 0;
153 status = 0;
154
155 while (1) { /* we will break */
156 /* Create a new block */
157 sems_tmp = (test_t *) malloc(sizeof(test_t));
158
159 if (sems_tmp == NULL) {
160 /* We stop here */
161 #if VERBOSE > 0
162 output("malloc failed with error %d (%s)\n", errno,
163 strerror(errno));
164 #endif
165 /* We can proceed anyway */
166 status = 1;
167
168 break;
169 }
170
171 /* read clock */
172 ret = clock_gettime(CLOCK_REALTIME, &ts_ref);
173
174 if (ret != 0) {
175 UNRESOLVED(errno, "Unable to read clock");
176 }
177
178 /* Open all semaphores in the current block */
179 for (i = 0; i < BLOCKSIZE; i++) {
180 ret = sem_init(&(sems_tmp->sems[i]), i & 1, i & 3);
181
182 if (ret != 0) {
183 #if VERBOSE > 0
184 output("sem_init failed with error %d (%s)\n",
185 errno, strerror(errno));
186 #endif
187 /* Check error code */
188 switch (errno) {
189 case EMFILE:
190 case ENFILE:
191 case ENOSPC:
192 case ENOMEM:
193 status = 2;
194 break;
195 default:
196 UNRESOLVED(errno, "Unexpected error!");
197
198 break;
199 }
200
201 if ((SEM_MAX > 0) && (nsem > SEM_MAX)) {
202 FAILED
203 ("sem_open opened more than SEM_NSEMS_MAX semaphores");
204 }
205
206 nsem++;
207 }
208
209 /* read clock */
210 ret = clock_gettime(CLOCK_REALTIME, &ts_fin);
211
212 if (ret != 0) {
213 UNRESOLVED(errno, "Unable to read clock");
214 }
215
216 if (status == 2) {
217 /* We were not able to fill this bloc, so we can discard it */
218
219 for (--i; i >= 0; i--) {
220 ret = sem_destroy(&(sems_tmp->sems[i]));
221
222 if (ret != 0) {
223 UNRESOLVED(errno,
224 "Failed to close");
225 }
226
227 }
228
229 free(sems_tmp);
230 break;
231
232 }
233
234 sems_tmp->prev = sems_cur;
235 sems_cur->next = sems_tmp;
236 sems_cur = sems_tmp;
237 sems_cur->next = NULL;
238
239 /* add to the measure list */
240 m_tmp = (mes_t *) malloc(sizeof(mes_t));
241
242 if (m_tmp == NULL) {
243 /* We stop here */
244 #if VERBOSE > 0
245 output("malloc failed with error %d (%s)\n",
246 errno, strerror(errno));
247 #endif
248 /* We can proceed anyway */
249 status = 3;
250
251 break;
252 }
253
254 m_tmp->nsem = nsem;
255 m_tmp->next = NULL;
256 m_tmp->prev = m_cur;
257 m_cur->next = m_tmp;
258
259 m_cur = m_tmp;
260
261 m_cur->_data_open =
262 ((ts_fin.tv_sec - ts_ref.tv_sec) * 1000000) +
263 ((ts_fin.tv_nsec - ts_ref.tv_nsec) / 1000);
264 m_cur->_data_close = 0;
265
266 if (nsem >= NSEM_LIMIT)
267 break;
268 }
269
270 locerrno = errno;
271
272 /* Free all semaphore blocs */
273 #if VERBOSE > 0
274 output("Detroy and free semaphores\n");
275
276 #endif
277
278 /* Reverse list order */
279
280 while (sems_cur != &sems) {
281 /* read clock */
282 ret = clock_gettime(CLOCK_REALTIME, &ts_ref);
283
284 if (ret != 0) {
285 UNRESOLVED(errno, "Unable to read clock");
286 }
287
288 /* Empty the sems_cur block */
289
290 for (i = 0; i < BLOCKSIZE; i++) {
291 ret = sem_destroy(&(sems_cur->sems[i]));
292
293 if (ret != 0) {
294 UNRESOLVED(errno,
295 "Failed to destroy a semaphore");
296 }
297 }
298
299 /* read clock */
300 ret = clock_gettime(CLOCK_REALTIME, &ts_fin);
301
302 if (ret != 0) {
303 UNRESOLVED(errno, "Unable to read clock");
304 }
305
306 /* add this measure to measure list */
307
308 m_cur->_data_close =
309 ((ts_fin.tv_sec - ts_ref.tv_sec) * 1000000) +
310 ((ts_fin.tv_nsec - ts_ref.tv_nsec) / 1000);
311
312 m_cur = m_cur->prev;
313
314 /* remove the sem bloc */
315 sems_cur = sems_cur->prev;
316
317 free(sems_cur->next);
318
319 sems_cur->next = NULL;
320 }
321
322 #if VERBOSE > 0
323 output("Parse results\n");
324
325 #endif
326
327 /* Compute the results */
328 ret = parse_measure(&sentinel);
329
330 /* Free the resources and output the results */
331
332 #if VERBOSE > 5
333 output("Dump : \n");
334
335 output(" nsem | open | close \n");
336
337 #endif
338
339 while (sentinel.next != NULL) {
340 m_cur = sentinel.next;
341 #if (VERBOSE > 5) || defined(PLOT_OUTPUT)
342 output("%8.8i %1.1li.%6.6li %1.1li.%6.6li\n",
343 m_cur->nsem, m_cur->_data_open / 1000000,
344 m_cur->_data_open % 1000000,
345 m_cur->_data_close / 1000000,
346 m_cur->_data_close % 1000000);
347
348 #endif
349 sentinel.next = m_cur->next;
350
351 free(m_cur);
352 }
353
354 if (ret != 0) {
355 FAILED
356 ("The function is not scalable, add verbosity for more information");
357 }
358
359 /* Check status */
360 if (status) {
361 UNRESOLVED(locerrno,
362 "Function is scalable, but test terminated with error");
363 }
364 #if VERBOSE > 0
365 output("-----\n");
366
367 output("All test data destroyed\n");
368
369 output("Test PASSED\n");
370
371 #endif
372
373 PASSED;
374 }
375
376 /***
377 * The next function will seek for the better model for each series of measurements.
378 *
379 * The tested models are: -- X = # threads; Y = latency
380 * -> Y = a; -- Error is r1 = avg((Y - Yavg)²);
381 * -> Y = aX + b; -- Error is r2 = avg((Y -aX -b)²);
382 * -- where a = avg ((X - Xavg)(Y - Yavg)) / avg((X - Xavg)²)
383 * -- Note: We will call _q = sum((X - Xavg) * (Y - Yavg));
384 * -- and _d = sum((X - Xavg)²);
385 * -- and b = Yavg - a * Xavg
386 * -> Y = c * X^a;-- Same as previous, but with log(Y) = a log(X) + b; and b = log(c). Error is r3
387 * -> Y = exp(aX + b); -- log(Y) = aX + b. Error is r4
388 *
389 * We compute each error factor (r1, r2, r3, r4) then search which is the smallest (with ponderation).
390 * The function returns 0 when r1 is the best for all cases (latency is constant) and !0 otherwise.
391 */
392
393 struct row {
394 long X; /* the X values -- copied from function argument */
395 long Y_o; /* the Y values -- copied from function argument */
396 long Y_c; /* the Y values -- copied from function argument */
397 long _x; /* Value X - Xavg */
398 long _y_o; /* Value Y - Yavg */
399 long _y_c; /* Value Y - Yavg */
400 double LnX; /* Natural logarithm of X values */
401 double LnY_o; /* Natural logarithm of Y values */
402 double LnY_c; /* Natural logarithm of Y values */
403 double _lnx; /* Value LnX - LnXavg */
404 double _lny_o; /* Value LnY - LnYavg */
405 double _lny_c; /* Value LnY - LnYavg */
406 };
407
408 int parse_measure(mes_t * measures) {
409 int ret, r;
410
411 mes_t *cur;
412
413 double Xavg, Yavg_o, Yavg_c;
414 double LnXavg, LnYavg_o, LnYavg_c;
415
416 int N;
417
418 double r1_o, r2_o, r3_o, r4_o;
419 double r1_c, r2_c, r3_c, r4_c;
420
421 /* Some more intermediate vars */
422 long double _q_o[3];
423 long double _d_o[3];
424 long double _q_c[3];
425 long double _d_c[3];
426
427 long double t; /* temp value */
428
429 struct row *Table = NULL;
430
431 /* This array contains the last element of each serie */
432 int array_max;
433
434 /* Initialize the datas */
435
436 array_max = -1; /* means no data */
437 Xavg = 0.0;
438 LnXavg = 0.0;
439 Yavg_o = 0.0;
440 LnYavg_o = 0.0;
441 r1_o = 0.0;
442 r2_o = 0.0;
443 r3_o = 0.0;
444 r4_o = 0.0;
445 _q_o[0] = 0.0;
446 _q_o[1] = 0.0;
447 _q_o[2] = 0.0;
448 _d_o[0] = 0.0;
449 _d_o[1] = 0.0;
450 _d_o[2] = 0.0;
451 Yavg_c = 0.0;
452 LnYavg_c = 0.0;
453 r1_c = 0.0;
454 r2_c = 0.0;
455 r3_c = 0.0;
456 r4_c = 0.0;
457 _q_c[0] = 0.0;
458 _q_c[1] = 0.0;
459 _q_c[2] = 0.0;
460 _d_c[0] = 0.0;
461 _d_c[1] = 0.0;
462 _d_c[2] = 0.0;
463
464 N = 0;
465 cur = measures;
466
467 #if VERBOSE > 1
468 output("Data analysis starting\n");
469 #endif
470
471 /* We start with reading the list to find:
472 * -> number of elements, to assign an array.
473 * -> average values
474 */
475
476 while (cur->next != NULL) {
477 cur = cur->next;
478
479 N++;
480
481 if (cur->_data_open != 0) {
482 array_max = N;
483 Xavg += (double)cur->nsem;
484 LnXavg += log((double)cur->nsem);
485 Yavg_o += (double)cur->_data_open;
486 LnYavg_o += log((double)cur->_data_open);
487 Yavg_c += (double)cur->_data_close;
488 LnYavg_c += log((double)cur->_data_close);
489 }
490
491 }
492
493 /* We have the sum; we can divide to obtain the average values */
494 if (array_max != -1) {
495 Xavg /= array_max;
496 LnXavg /= array_max;
497 Yavg_o /= array_max;
498 LnYavg_o /= array_max;
499 Yavg_c /= array_max;
500 LnYavg_c /= array_max;
501 }
502 #if VERBOSE > 1
503 output(" Found %d rows\n", N);
504
505 #endif
506
507 /* We will now alloc the array ... */
508
509 Table = calloc(N, sizeof(struct row));
510
511 if (Table == NULL) {
512 UNRESOLVED(errno,
513 "Unable to alloc space for results parsing");
514 }
515
516 /* ... and fill it */
517 N = 0;
518
519 cur = measures;
520
521 while (cur->next != NULL) {
522 cur = cur->next;
523
524 Table[N].X = (long)cur->nsem;
525 Table[N].LnX = log((double)cur->nsem);
526
527 if (array_max > N) {
528 Table[N]._x = Table[N].X - Xavg;
529 Table[N]._lnx = Table[N].LnX - LnXavg;
530 Table[N].Y_o = cur->_data_open;
531 Table[N]._y_o = Table[N].Y_o - Yavg_o;
532 Table[N].LnY_o = log((double)cur->_data_open);
533 Table[N]._lny_o = Table[N].LnY_o - LnYavg_o;
534 Table[N].Y_c = cur->_data_close;
535 Table[N]._y_c = Table[N].Y_c - Yavg_c;
536 Table[N].LnY_c = log((double)cur->_data_close);
537 Table[N]._lny_c = Table[N].LnY_c - LnYavg_c;
538 }
539
540 N++;
541 }
542
543 /* We won't need the list anymore -- we'll work with the array which should be faster. */
544 #if VERBOSE > 1
545 output(" Data was stored in an array.\n");
546
547 #endif
548
549 /* We need to read the full array at least twice to compute all the error factors */
550
551 /* In the first pass, we'll compute:
552 * -> r1 for each scenar.
553 * -> "a" factor for linear (0), power (1) and exponential (2) approximations -- with using the _d and _q vars.
554 */
555 #if VERBOSE > 1
556 output("Starting first pass...\n");
557
558 #endif
559 for (r = 0; r < array_max; r++) {
560 r1_o +=
561 ((double)Table[r]._y_o / array_max) *
562 (double)Table[r]._y_o;
563
564 _q_o[0] += Table[r]._y_o * Table[r]._x;
565 _d_o[0] += Table[r]._x * Table[r]._x;
566
567 _q_o[1] += Table[r]._lny_o * Table[r]._lnx;
568 _d_o[1] += Table[r]._lnx * Table[r]._lnx;
569
570 _q_o[2] += Table[r]._lny_o * Table[r]._x;
571 _d_o[2] += Table[r]._x * Table[r]._x;
572
573 r1_c +=
574 ((double)Table[r]._y_c / array_max) *
575 (double)Table[r]._y_c;
576
577 _q_c[0] += Table[r]._y_c * Table[r]._x;
578 _d_c[0] += Table[r]._x * Table[r]._x;
579
580 _q_c[1] += Table[r]._lny_c * Table[r]._lnx;
581 _d_c[1] += Table[r]._lnx * Table[r]._lnx;
582
583 _q_c[2] += Table[r]._lny_c * Table[r]._x;
584 _d_c[2] += Table[r]._x * Table[r]._x;
585
586 }
587
588 /* First pass is terminated; a2 = _q[0]/_d[0]; a3 = _q[1]/_d[1]; a4 = _q[2]/_d[2] */
589
590 /* In the first pass, we'll compute:
591 * -> r2, r3, r4 for each scenar.
592 */
593
594 #if VERBOSE > 1
595 output("Starting second pass...\n");
596
597 #endif
598 for (r = 0; r < array_max; r++) {
599 /* r2 = avg((y - ax -b)²); t = (y - ax - b) = (y - yavg) - a (x - xavg); */
600 t = (Table[r]._y_o -
601 ((_q_o[0] * Table[r]._x) / _d_o[0]));
602 r2_o += t * t / array_max;
603
604 t = (Table[r]._y_c -
605 ((_q_c[0] * Table[r]._x) / _d_c[0]));
606 r2_c += t * t / array_max;
607
608 /* r3 = avg((y - c.x^a) ²);
609 t = y - c * x ^ a
610 = y - log (LnYavg - (_q[1]/_d[1]) * LnXavg) * x ^ (_q[1]/_d[1])
611 */
612 t = (Table[r].Y_o
613 - (logl(LnYavg_o - (_q_o[1] / _d_o[1]) * LnXavg)
614 * powl(Table[r].X, (_q_o[1] / _d_o[1]))
615 ));
616 r3_o += t * t / array_max;
617
618 t = (Table[r].Y_c
619 - (logl(LnYavg_c - (_q_c[1] / _d_c[1]) * LnXavg)
620 * powl(Table[r].X, (_q_c[1] / _d_c[1]))
621 ));
622 r3_c += t * t / array_max;
623
624 /* r4 = avg((y - exp(ax+b))²);
625 t = y - exp(ax+b)
626 = y - exp(_q[2]/_d[2] * x + (LnYavg - (_q[2]/_d[2] * Xavg)));
627 = y - exp(_q[2]/_d[2] * (x - Xavg) + LnYavg);
628 */
629 t = (Table[r].Y_o
630 - expl((_q_o[2] / _d_o[2]) * Table[r]._x +
631 LnYavg_o));
632 r4_o += t * t / array_max;
633
634 t = (Table[r].Y_c
635 - expl((_q_c[2] / _d_c[2]) * Table[r]._x +
636 LnYavg_c));
637 r4_c += t * t / array_max;
638
639 }
640
641 #if VERBOSE > 1
642 output("All computing terminated.\n");
643
644 #endif
645 ret = 0;
646
647 #if VERBOSE > 1
648 output(" # of data: %i\n", array_max);
649
650 output(" Model: Y = k\n");
651
652 output(" sem_open:\n");
653
654 output(" k = %g\n", Yavg_o);
655
656 output(" Divergence %g\n", r1_o);
657
658 output(" sem_close:\n");
659
660 output(" k = %g\n", Yavg_c);
661
662 output(" Divergence %g\n", r1_c);
663
664 output(" Model: Y = a * X + b\n");
665
666 output(" sem_open:\n");
667
668 output(" a = %Lg\n", _q_o[0] / _d_o[0]);
669
670 output(" b = %Lg\n",
671 Yavg_o - ((_q_o[0] / _d_o[0]) * Xavg));
672
673 output(" Divergence %g\n", r2_o);
674
675 output(" sem_close:\n");
676
677 output(" a = %Lg\n", _q_c[0] / _d_c[0]);
678
679 output(" b = %Lg\n",
680 Yavg_c - ((_q_c[0] / _d_c[0]) * Xavg));
681
682 output(" Divergence %g\n", r2_c);
683
684 output(" Model: Y = c * X ^ a\n");
685
686 output(" sem_open:\n");
687
688 output(" a = %Lg\n", _q_o[1] / _d_o[1]);
689
690 output(" c = %Lg\n",
691 logl(LnYavg_o - (_q_o[1] / _d_o[1]) * LnXavg));
692
693 output(" Divergence %g\n", r3_o);
694
695 output(" sem_close:\n");
696
697 output(" a = %Lg\n", _q_c[1] / _d_c[1]);
698
699 output(" c = %Lg\n",
700 logl(LnYavg_c - (_q_c[1] / _d_c[1]) * LnXavg));
701
702 output(" Divergence %g\n", r3_c);
703
704 output(" Model: Y = exp(a * X + b)\n");
705
706 output(" sem_open:\n");
707
708 output(" a = %Lg\n", _q_o[2] / _d_o[2]);
709
710 output(" b = %Lg\n",
711 LnYavg_o - ((_q_o[2] / _d_o[2]) * Xavg));
712
713 output(" Divergence %g\n", r4_o);
714
715 output(" sem_close:\n");
716
717 output(" a = %Lg\n", _q_c[2] / _d_c[2]);
718
719 output(" b = %Lg\n",
720 LnYavg_c - ((_q_c[2] / _d_c[2]) * Xavg));
721
722 output(" Divergence %g\n", r4_c);
723
724 #endif
725
726 if (array_max != -1) {
727 /* Compare r1 to other values, with some ponderations */
728
729 if ((r1_o > 1.1 * r2_o) || (r1_o > 1.2 * r3_o) ||
730 (r1_o > 1.3 * r4_o) || (r1_c > 1.1 * r2_c) ||
731 (r1_c > 1.2 * r3_c) || (r1_c > 1.3 * r4_c))
732 ret++;
733
734 #if VERBOSE > 1
735 else
736 output(" Sanction: OK\n");
737
738 #endif
739
740 }
741
742 /* We need to free the array */
743 free(Table);
744
745 /* We're done */
746 return ret;
747 }
748