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