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