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 */ 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