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 static 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 /***
378 * The next function will seek for the better model for each series of measurements.
379 *
380 * The tested models are: -- X = # threads; Y = latency
381 * -> Y = a; -- Error is r1 = avg((Y - Yavg)²);
382 * -> Y = aX + b; -- Error is r2 = avg((Y -aX -b)²);
383 * -- where a = avg ((X - Xavg)(Y - Yavg)) / avg((X - Xavg)²)
384 * -- Note: We will call _q = sum((X - Xavg) * (Y - Yavg));
385 * -- and _d = sum((X - Xavg)²);
386 * -- and b = Yavg - a * Xavg
387 * -> Y = c * X^a;-- Same as previous, but with log(Y) = a log(X) + b; and b = log(c). Error is r3
388 * -> Y = exp(aX + b); -- log(Y) = aX + b. Error is r4
389 *
390 * We compute each error factor (r1, r2, r3, r4) then search which is the smallest (with ponderation).
391 * The function returns 0 when r1 is the best for all cases (latency is constant) and !0 otherwise.
392 */
393
394 struct row {
395 long X; /* the X values -- copied from function argument */
396 long Y_o; /* the Y values -- copied from function argument */
397 long Y_c; /* the Y values -- copied from function argument */
398 long _x; /* Value X - Xavg */
399 long _y_o; /* Value Y - Yavg */
400 long _y_c; /* Value Y - Yavg */
401 double LnX; /* Natural logarithm of X values */
402 double LnY_o; /* Natural logarithm of Y values */
403 double LnY_c; /* Natural logarithm of Y values */
404 double _lnx; /* Value LnX - LnXavg */
405 double _lny_o; /* Value LnY - LnYavg */
406 double _lny_c; /* Value LnY - LnYavg */
407 };
408
parse_measure(mes_t * measures)409 int parse_measure(mes_t * measures) {
410 int ret, r;
411
412 mes_t *cur;
413
414 double Xavg, Yavg_o, Yavg_c;
415 double LnXavg, LnYavg_o, LnYavg_c;
416
417 int N;
418
419 double r1_o, r2_o, r3_o, r4_o;
420 double r1_c, r2_c, r3_c, r4_c;
421
422 /* Some more intermediate vars */
423 long double _q_o[3];
424 long double _d_o[3];
425 long double _q_c[3];
426 long double _d_c[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_o = 0.0;
441 LnYavg_o = 0.0;
442 r1_o = 0.0;
443 r2_o = 0.0;
444 r3_o = 0.0;
445 r4_o = 0.0;
446 _q_o[0] = 0.0;
447 _q_o[1] = 0.0;
448 _q_o[2] = 0.0;
449 _d_o[0] = 0.0;
450 _d_o[1] = 0.0;
451 _d_o[2] = 0.0;
452 Yavg_c = 0.0;
453 LnYavg_c = 0.0;
454 r1_c = 0.0;
455 r2_c = 0.0;
456 r3_c = 0.0;
457 r4_c = 0.0;
458 _q_c[0] = 0.0;
459 _q_c[1] = 0.0;
460 _q_c[2] = 0.0;
461 _d_c[0] = 0.0;
462 _d_c[1] = 0.0;
463 _d_c[2] = 0.0;
464
465 N = 0;
466 cur = measures;
467
468 #if VERBOSE > 1
469 output("Data analysis starting\n");
470 #endif
471
472 /* We start with reading the list to find:
473 * -> number of elements, to assign an array.
474 * -> average values
475 */
476
477 while (cur->next != NULL) {
478 cur = cur->next;
479
480 N++;
481
482 if (cur->_data_open != 0) {
483 array_max = N;
484 Xavg += (double)cur->nsem;
485 LnXavg += log((double)cur->nsem);
486 Yavg_o += (double)cur->_data_open;
487 LnYavg_o += log((double)cur->_data_open);
488 Yavg_c += (double)cur->_data_close;
489 LnYavg_c += log((double)cur->_data_close);
490 }
491
492 }
493
494 /* We have the sum; we can divide to obtain the average values */
495 if (array_max != -1) {
496 Xavg /= array_max;
497 LnXavg /= array_max;
498 Yavg_o /= array_max;
499 LnYavg_o /= array_max;
500 Yavg_c /= array_max;
501 LnYavg_c /= array_max;
502 }
503 #if VERBOSE > 1
504 output(" Found %d rows\n", N);
505
506 #endif
507
508 /* We will now alloc the array ... */
509
510 Table = calloc(N, sizeof(struct row));
511
512 if (Table == NULL) {
513 UNRESOLVED(errno,
514 "Unable to alloc space for results parsing");
515 }
516
517 /* ... and fill it */
518 N = 0;
519
520 cur = measures;
521
522 while (cur->next != NULL) {
523 cur = cur->next;
524
525 Table[N].X = (long)cur->nsem;
526 Table[N].LnX = log((double)cur->nsem);
527
528 if (array_max > N) {
529 Table[N]._x = Table[N].X - Xavg;
530 Table[N]._lnx = Table[N].LnX - LnXavg;
531 Table[N].Y_o = cur->_data_open;
532 Table[N]._y_o = Table[N].Y_o - Yavg_o;
533 Table[N].LnY_o = log((double)cur->_data_open);
534 Table[N]._lny_o = Table[N].LnY_o - LnYavg_o;
535 Table[N].Y_c = cur->_data_close;
536 Table[N]._y_c = Table[N].Y_c - Yavg_c;
537 Table[N].LnY_c = log((double)cur->_data_close);
538 Table[N]._lny_c = Table[N].LnY_c - LnYavg_c;
539 }
540
541 N++;
542 }
543
544 /* We won't need the list anymore -- we'll work with the array which should be faster. */
545 #if VERBOSE > 1
546 output(" Data was stored in an array.\n");
547
548 #endif
549
550 /* We need to read the full array at least twice to compute all the error factors */
551
552 /* In the first pass, we'll compute:
553 * -> r1 for each scenar.
554 * -> "a" factor for linear (0), power (1) and exponential (2) approximations -- with using the _d and _q vars.
555 */
556 #if VERBOSE > 1
557 output("Starting first pass...\n");
558
559 #endif
560 for (r = 0; r < array_max; r++) {
561 r1_o +=
562 ((double)Table[r]._y_o / array_max) *
563 (double)Table[r]._y_o;
564
565 _q_o[0] += Table[r]._y_o * Table[r]._x;
566 _d_o[0] += Table[r]._x * Table[r]._x;
567
568 _q_o[1] += Table[r]._lny_o * Table[r]._lnx;
569 _d_o[1] += Table[r]._lnx * Table[r]._lnx;
570
571 _q_o[2] += Table[r]._lny_o * Table[r]._x;
572 _d_o[2] += Table[r]._x * Table[r]._x;
573
574 r1_c +=
575 ((double)Table[r]._y_c / array_max) *
576 (double)Table[r]._y_c;
577
578 _q_c[0] += Table[r]._y_c * Table[r]._x;
579 _d_c[0] += Table[r]._x * Table[r]._x;
580
581 _q_c[1] += Table[r]._lny_c * Table[r]._lnx;
582 _d_c[1] += Table[r]._lnx * Table[r]._lnx;
583
584 _q_c[2] += Table[r]._lny_c * Table[r]._x;
585 _d_c[2] += Table[r]._x * Table[r]._x;
586
587 }
588
589 /* First pass is terminated; a2 = _q[0]/_d[0]; a3 = _q[1]/_d[1]; a4 = _q[2]/_d[2] */
590
591 /* In the first pass, we'll compute:
592 * -> r2, r3, r4 for each scenar.
593 */
594
595 #if VERBOSE > 1
596 output("Starting second pass...\n");
597
598 #endif
599 for (r = 0; r < array_max; r++) {
600 /* r2 = avg((y - ax -b)²); t = (y - ax - b) = (y - yavg) - a (x - xavg); */
601 t = (Table[r]._y_o -
602 ((_q_o[0] * Table[r]._x) / _d_o[0]));
603 r2_o += t * t / array_max;
604
605 t = (Table[r]._y_c -
606 ((_q_c[0] * Table[r]._x) / _d_c[0]));
607 r2_c += t * t / array_max;
608
609 /* r3 = avg((y - c.x^a) ²);
610 t = y - c * x ^ a
611 = y - log (LnYavg - (_q[1]/_d[1]) * LnXavg) * x ^ (_q[1]/_d[1])
612 */
613 t = (Table[r].Y_o
614 - (logl(LnYavg_o - (_q_o[1] / _d_o[1]) * LnXavg)
615 * powl(Table[r].X, (_q_o[1] / _d_o[1]))
616 ));
617 r3_o += t * t / array_max;
618
619 t = (Table[r].Y_c
620 - (logl(LnYavg_c - (_q_c[1] / _d_c[1]) * LnXavg)
621 * powl(Table[r].X, (_q_c[1] / _d_c[1]))
622 ));
623 r3_c += t * t / array_max;
624
625 /* r4 = avg((y - exp(ax+b))²);
626 t = y - exp(ax+b)
627 = y - exp(_q[2]/_d[2] * x + (LnYavg - (_q[2]/_d[2] * Xavg)));
628 = y - exp(_q[2]/_d[2] * (x - Xavg) + LnYavg);
629 */
630 t = (Table[r].Y_o
631 - expl((_q_o[2] / _d_o[2]) * Table[r]._x +
632 LnYavg_o));
633 r4_o += t * t / array_max;
634
635 t = (Table[r].Y_c
636 - expl((_q_c[2] / _d_c[2]) * Table[r]._x +
637 LnYavg_c));
638 r4_c += t * t / array_max;
639
640 }
641
642 #if VERBOSE > 1
643 output("All computing terminated.\n");
644
645 #endif
646 ret = 0;
647
648 #if VERBOSE > 1
649 output(" # of data: %i\n", array_max);
650
651 output(" Model: Y = k\n");
652
653 output(" sem_open:\n");
654
655 output(" k = %g\n", Yavg_o);
656
657 output(" Divergence %g\n", r1_o);
658
659 output(" sem_close:\n");
660
661 output(" k = %g\n", Yavg_c);
662
663 output(" Divergence %g\n", r1_c);
664
665 output(" Model: Y = a * X + b\n");
666
667 output(" sem_open:\n");
668
669 output(" a = %Lg\n", _q_o[0] / _d_o[0]);
670
671 output(" b = %Lg\n",
672 Yavg_o - ((_q_o[0] / _d_o[0]) * Xavg));
673
674 output(" Divergence %g\n", r2_o);
675
676 output(" sem_close:\n");
677
678 output(" a = %Lg\n", _q_c[0] / _d_c[0]);
679
680 output(" b = %Lg\n",
681 Yavg_c - ((_q_c[0] / _d_c[0]) * Xavg));
682
683 output(" Divergence %g\n", r2_c);
684
685 output(" Model: Y = c * X ^ a\n");
686
687 output(" sem_open:\n");
688
689 output(" a = %Lg\n", _q_o[1] / _d_o[1]);
690
691 output(" c = %Lg\n",
692 logl(LnYavg_o - (_q_o[1] / _d_o[1]) * LnXavg));
693
694 output(" Divergence %g\n", r3_o);
695
696 output(" sem_close:\n");
697
698 output(" a = %Lg\n", _q_c[1] / _d_c[1]);
699
700 output(" c = %Lg\n",
701 logl(LnYavg_c - (_q_c[1] / _d_c[1]) * LnXavg));
702
703 output(" Divergence %g\n", r3_c);
704
705 output(" Model: Y = exp(a * X + b)\n");
706
707 output(" sem_open:\n");
708
709 output(" a = %Lg\n", _q_o[2] / _d_o[2]);
710
711 output(" b = %Lg\n",
712 LnYavg_o - ((_q_o[2] / _d_o[2]) * Xavg));
713
714 output(" Divergence %g\n", r4_o);
715
716 output(" sem_close:\n");
717
718 output(" a = %Lg\n", _q_c[2] / _d_c[2]);
719
720 output(" b = %Lg\n",
721 LnYavg_c - ((_q_c[2] / _d_c[2]) * Xavg));
722
723 output(" Divergence %g\n", r4_c);
724
725 #endif
726
727 if (array_max != -1) {
728 /* Compare r1 to other values, with some ponderations */
729
730 if ((r1_o > 1.1 * r2_o) || (r1_o > 1.2 * r3_o) ||
731 (r1_o > 1.3 * r4_o) || (r1_c > 1.1 * r2_c) ||
732 (r1_c > 1.2 * r3_c) || (r1_c > 1.3 * r4_c))
733 ret++;
734
735 #if VERBOSE > 1
736 else
737 output(" Sanction: OK\n");
738
739 #endif
740
741 }
742
743 /* We need to free the array */
744 free(Table);
745
746 /* We're done */
747 return ret;
748 }
749