1/* 2 * Copyright (c) 2004, 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., 59 15 * Temple Place - Suite 330, Boston MA 02111-1307, USA. 16 17 18 * This scalability sample aims to test the following assertions: 19 * -> If pthread_create fails because of a lack of a resource, or 20 PTHREAD_THREADS_MAX threads already exist, EAGAIN shall be returned. 21 * -> It also tests that the thread creation time does not depend on the # of threads 22 * already created. 23 24 * The steps are: 25 * -> Create threads until failure 26 27 */ 28 29 30 /* We are testing conformance to IEEE Std 1003.1, 2003 Edition */ 31 #define _POSIX_C_SOURCE 200112L 32 33 /* Some routines are part of the XSI Extensions */ 34#ifndef WITHOUT_XOPEN 35 #define _XOPEN_SOURCE 600 36#endif 37/********************************************************************************************/ 38/****************************** standard includes *****************************************/ 39/********************************************************************************************/ 40 #include <pthread.h> 41 #include <stdarg.h> 42 #include <stdio.h> 43 #include <stdlib.h> 44 #include <string.h> 45 #include <unistd.h> 46 47 #include <sched.h> 48 #include <semaphore.h> 49 #include <errno.h> 50 #include <assert.h> 51 #include <sys/wait.h> 52 #include <math.h> 53 54 55/********************************************************************************************/ 56/****************************** Test framework *****************************************/ 57/********************************************************************************************/ 58 #include "testfrmw.h" 59 #include "testfrmw.c" 60 /* This header is responsible for defining the following macros: 61 * UNRESOLVED(ret, descr); 62 * where descr is a description of the error and ret is an int (error code for example) 63 * FAILED(descr); 64 * where descr is a short text saying why the test has failed. 65 * PASSED(); 66 * No parameter. 67 * 68 * Both three macros shall terminate the calling process. 69 * The testcase shall not terminate in any other maneer. 70 * 71 * The other file defines the functions 72 * void output_init() 73 * void output(char * string, ...) 74 * 75 * Those may be used to output information. 76 */ 77 78/********************************************************************************************/ 79/********************************** Configuration ******************************************/ 80/********************************************************************************************/ 81#ifndef SCALABILITY_FACTOR 82#define SCALABILITY_FACTOR 1 83#endif 84#ifndef VERBOSE 85#define VERBOSE 1 86#endif 87 88#define RESOLUTION (5 * SCALABILITY_FACTOR) 89 90#ifdef PLOT_OUTPUT 91#undef VERBOSE 92#define VERBOSE 0 93#endif 94 95/********************************************************************************************/ 96/*********************************** Test cases *****************************************/ 97/********************************************************************************************/ 98 99#include "threads_scenarii.c" 100 101/* This file will define the following objects: 102 * scenarii: array of struct __scenario type. 103 * NSCENAR : macro giving the total # of scenarii 104 * scenar_init(): function to call before use the scenarii array. 105 * scenar_fini(): function to call after end of use of the scenarii array. 106 */ 107 108 109/********************************************************************************************/ 110/*********************************** Real Test *****************************************/ 111/********************************************************************************************/ 112 113/* The next structure is used to save the tests measures */ 114typedef struct __mes_t 115{ 116 int nthreads; 117 long _data[ NSCENAR ]; /* As we store µsec values, a long type should be amply enough. */ 118 struct __mes_t *next; 119} mes_t; 120 121/* Forward declaration */ 122int parse_measure(mes_t * measures); 123 124 125 126pthread_mutex_t m_synchro=PTHREAD_MUTEX_INITIALIZER; 127 128void * threaded(void * arg) 129{ 130 int ret=0; 131 132 /* Signal we're done */ 133 do { ret = sem_post(&scenarii[sc].sem); } 134 while ((ret == -1) && (errno == EINTR)); 135 if (ret == -1) { UNRESOLVED(errno, "Failed to wait for the semaphore"); } 136 137 /* Wait for all threads being created */ 138 ret = pthread_mutex_lock(&m_synchro); 139 if (ret != 0) { UNRESOLVED(ret, "Mutex lock failed"); } 140 (*(int *)arg) += 1; 141 ret = pthread_mutex_unlock(&m_synchro); 142 if (ret != 0) { UNRESOLVED(ret, "Mutex unlock failed"); } 143 144 return arg; 145} 146 147int main (int argc, char *argv[]) 148{ 149 int ret=0; 150 pthread_t child; 151 pthread_t *th; 152 153 int nthreads, ctl, i, tmp; 154 155 struct timespec ts_ref, ts_fin; 156 157 mes_t sentinel; 158 mes_t *m_cur, *m_tmp; 159 160 long PTHREAD_THREADS_MAX = sysconf(_SC_THREAD_THREADS_MAX); 161 long my_max = 1000 * SCALABILITY_FACTOR ; 162 163 /* Initialize the measure list */ 164 m_cur = &sentinel; 165 m_cur->next = NULL; 166 167 /* Initialize output routine */ 168 output_init(); 169 170 if (PTHREAD_THREADS_MAX > 0) 171 my_max = PTHREAD_THREADS_MAX; 172 173 th = (pthread_t *)calloc(1 + my_max, sizeof(pthread_t)); 174 if (th == NULL) { UNRESOLVED(errno, "Not enough memory for thread storage"); } 175 176 /* Initialize thread attribute objects */ 177 scenar_init(); 178 179 #ifdef PLOT_OUTPUT 180 printf("# COLUMNS %d #threads", NSCENAR + 1); 181 for (sc=0; sc<NSCENAR; sc++) 182 printf(" %i", sc); 183 printf("\n"); 184 #endif 185 186 for (sc=0; sc < NSCENAR; sc++) 187 { 188 if (scenarii[sc].bottom == NULL) /* skip the alternate stacks as we could create only 1 */ 189 { 190 #if VERBOSE > 0 191 output("-----\n"); 192 output("Starting test with scenario (%i): %s\n", sc, scenarii[sc].descr); 193 #endif 194 195 /* Block every (about to be) created threads */ 196 ret = pthread_mutex_lock(&m_synchro); 197 if (ret != 0) { UNRESOLVED(ret, "Mutex lock failed"); } 198 199 ctl=0; 200 nthreads=0; 201 m_cur = &sentinel; 202 203 /* Create 1 thread for testing purpose */ 204 ret = pthread_create(&child, &scenarii[sc].ta, threaded, &ctl); 205 switch (scenarii[sc].result) 206 { 207 case 0: /* Operation was expected to succeed */ 208 if (ret != 0) { UNRESOLVED(ret, "Failed to create this thread"); } 209 break; 210 211 case 1: /* Operation was expected to fail */ 212 if (ret == 0) { UNRESOLVED(-1, "An error was expected but the thread creation succeeded"); } 213 break; 214 215 case 2: /* We did not know the expected result */ 216 default: 217 #if VERBOSE > 0 218 if (ret == 0) 219 { output("Thread has been created successfully for this scenario\n"); } 220 else 221 { output("Thread creation failed with the error: %s\n", strerror(ret)); } 222 #endif 223 ; 224 } 225 if (ret == 0) /* The new thread is running */ 226 { 227 228 while (1) /* we will break */ 229 { 230 /* read clock */ 231 ret = clock_gettime(CLOCK_REALTIME, &ts_ref); 232 if (ret != 0) { UNRESOLVED(errno, "Unable to read clock"); } 233 234 /* create a new thread */ 235 ret = pthread_create(&th[nthreads], &scenarii[sc].ta, threaded, &ctl); 236 237 /* stop here if we've got EAGAIN */ 238 if (ret == EAGAIN) 239 break; 240 241// temporary hack 242if (ret == ENOMEM) break; 243 nthreads++; 244 245 /* FAILED if error is != EAGAIN or nthreads > PTHREAD_THREADS_MAX */ 246 if (ret != 0) 247 { 248 output("pthread_create returned: %i (%s)\n", ret, strerror(ret)); 249 FAILED("pthread_create did not return EAGAIN on a lack of resource"); 250 } 251 if (nthreads > my_max) 252 { 253 if (PTHREAD_THREADS_MAX > 0) 254 { 255 FAILED("We were able to create more than PTHREAD_THREADS_MAX threads"); 256 } 257 else 258 { 259 break; 260 } 261 } 262 263 /* wait for the semaphore */ 264 do { ret = sem_wait(&scenarii[sc].sem); } 265 while ((ret == -1) && (errno == EINTR)); 266 if (ret == -1) { UNRESOLVED(errno, "Failed to wait for the semaphore"); } 267 268 /* read clock */ 269 ret = clock_gettime(CLOCK_REALTIME, &ts_fin); 270 if (ret != 0) { UNRESOLVED(errno, "Unable to read clock"); } 271 272 /* add to the measure list if nthreads % resolution == 0 */ 273 if ((nthreads % RESOLUTION) == 0) 274 { 275 if (m_cur->next == NULL) 276 { 277 /* Create an empty new element */ 278 m_tmp = (mes_t *) malloc(sizeof(mes_t)); 279 if (m_tmp == NULL) { UNRESOLVED(errno, "Unable to alloc memory for measure saving"); } 280 m_tmp->nthreads = nthreads; 281 m_tmp->next = NULL; 282 for (tmp=0; tmp<NSCENAR; tmp++) 283 m_tmp->_data[tmp]= 0; 284 m_cur->next = m_tmp; 285 } 286 287 /* Add this measure to the next element */ 288 m_cur = m_cur->next; 289 m_cur->_data[sc] = ((ts_fin.tv_sec - ts_ref.tv_sec) * 1000000) + ((ts_fin.tv_nsec - ts_ref.tv_nsec) / 1000) ; 290 291 #if VERBOSE > 5 292 output("Added the following measure: sc=%i, n=%i, v=%li\n", sc, nthreads, m_cur->_data[sc]); 293 #endif 294 } 295 } 296 #if VERBOSE > 3 297 output("Could not create anymore thread. Current count is %i\n", nthreads); 298 #endif 299 300 /* Unblock every created threads */ 301 ret = pthread_mutex_unlock(&m_synchro); 302 if (ret != 0) { UNRESOLVED(ret, "Mutex unlock failed"); } 303 304 if (scenarii[sc].detached == 0) 305 { 306 #if VERBOSE > 3 307 output("Joining the threads\n"); 308 #endif 309 for (i = 0; i < nthreads; i++) 310 { 311 ret = pthread_join(th[i], NULL); 312 if (ret != 0) { UNRESOLVED(ret, "Unable to join a thread"); } 313 } 314 315 ret = pthread_join(child, NULL); 316 if (ret != 0) { UNRESOLVED(ret, "Unalbe to join a thread"); } 317 318 } 319 #if VERBOSE > 3 320 output("Waiting for threads (almost) termination\n"); 321 #endif 322 do { 323 ret = pthread_mutex_lock(&m_synchro); 324 if (ret != 0) { UNRESOLVED(ret, "Mutex lock failed"); } 325 326 tmp = ctl; 327 328 ret = pthread_mutex_unlock(&m_synchro); 329 if (ret != 0) { UNRESOLVED(ret, "Mutex unlock failed"); } 330 } while (tmp != nthreads + 1); 331 332 } /* The thread was created */ 333 334 } } /* next scenario */ 335 336 /* Free some memory before result parsing */ 337 free(th); 338 339 /* Compute the results */ 340 ret = parse_measure(&sentinel); 341 342 343 /* Free the resources and output the results */ 344 345 #if VERBOSE > 5 346 printf("Dump : \n"); 347 printf("%8.8s", "nth"); 348 for (i = 0; i<NSCENAR; i++) 349 printf("| %2.2i ", i); 350 printf("\n"); 351 #endif 352 while (sentinel.next != NULL) 353 { 354 m_cur = sentinel.next; 355 #if (VERBOSE > 5) || defined(PLOT_OUTPUT) 356 printf("%8.8i", m_cur->nthreads); 357 for (i=0; i<NSCENAR; i++) 358 printf(" %1.1li.%6.6li", m_cur->_data[i] / 1000000, m_cur->_data[i] % 1000000); 359 printf("\n"); 360 #endif 361 sentinel.next = m_cur->next; 362 free(m_cur); 363 } 364 365 scenar_fini(); 366 367 #if VERBOSE > 0 368 output("-----\n"); 369 output("All test data destroyed\n"); 370 output("Test PASSED\n"); 371 #endif 372 373 PASSED; 374} 375 376 377 378 379 380/*** 381 * The next function will seek for the better model for each series of measurements. 382 * 383 * The tested models are: -- X = # threads; Y = latency 384 * -> Y = a; -- Error is r1 = avg( (Y - Yavg)² ); 385 * -> Y = aX + b; -- Error is r2 = avg( (Y -aX -b)² ); 386 * -- where a = avg ( (X - Xavg)(Y - Yavg) ) / avg( ( X - Xavg)² ) 387 * -- Note: We will call _q = sum( (X - Xavg) * (Y - Yavg) ); 388 * -- and _d = sum( (X - Xavg)² ); 389 * -- and b = Yavg - a * Xavg 390 * -> Y = c * X^a;-- Same as previous, but with log(Y) = a log(X) + b; and b = log(c). Error is r3 391 * -> Y = exp(aX + b); -- log(Y) = aX + b. Error is r4 392 * 393 * We compute each error factor (r1, r2, r3, r4) then search which is the smallest (with ponderation). 394 * The function returns 0 when r1 is the best for all cases (latency is constant) and !0 otherwise. 395 */ 396 397struct row 398{ 399 long X; /* the X values -- copied from function argument */ 400 long Y[NSCENAR]; /* the Y values -- copied from function argument */ 401 long _x[NSCENAR]; /* Value X - Xavg */ 402 long _y[NSCENAR]; /* Value Y - Yavg */ 403 double LnX; /* Natural logarithm of X values */ 404 double LnY[NSCENAR]; /* Natural logarithm of Y values */ 405 double _lnx[NSCENAR]; /* Value LnX - LnXavg */ 406 double _lny[NSCENAR]; /* Value LnY - LnYavg */ 407}; 408 409int parse_measure(mes_t * measures) 410{ 411 int ret, i, r; 412 413 mes_t *cur; 414 415 double Xavg[NSCENAR], Yavg[NSCENAR]; 416 double LnXavg[NSCENAR], LnYavg[NSCENAR]; 417 418 int N; 419 420 double r1[NSCENAR], r2[NSCENAR], r3[NSCENAR], r4[NSCENAR]; 421 422 /* Some more intermediate vars */ 423 long double _q[3][NSCENAR]; 424 long double _d[3][NSCENAR]; 425 426 long double t; /* temp value */ 427 428 struct row *Table = NULL; 429 430 /* This array contains the last element of each serie */ 431 int array_max[NSCENAR]; 432 433 /* Initialize the datas */ 434 for (i=0; i<NSCENAR; i++) 435 { 436 array_max[i] = -1; /* means no data */ 437 Xavg[i] = 0.0; 438 LnXavg[i] = 0.0; 439 Yavg[i] = 0.0; 440 LnYavg[i] = 0.0; 441 r1[i] = 0.0; 442 r2[i] = 0.0; 443 r3[i] = 0.0; 444 r4[i] = 0.0; 445 _q[0][i]=0.0; 446 _q[1][i]=0.0; 447 _q[2][i]=0.0; 448 _d[0][i]=0.0; 449 _d[1][i]=0.0; 450 _d[2][i]=0.0; 451 } 452 N=0; 453 cur = measures; 454 455 #if VERBOSE > 1 456 output("Data analysis starting\n"); 457 #endif 458 459 /* We start with reading the list to find: 460 * -> number of elements, to assign an array. 461 * -> average values 462 */ 463 while (cur->next != NULL) 464 { 465 cur = cur->next; 466 467 N++; 468 469 for (i=0; i<NSCENAR; i++) 470 { 471 if (cur->_data[i] != 0) 472 { 473 array_max[i]=N; 474 Xavg[i] += (double) cur->nthreads; 475 LnXavg[i] += log( (double) cur->nthreads); 476 Yavg[i] += (double) cur->_data[i]; 477 LnYavg[i] += log( (double) cur->_data[i] ); 478 } 479 } 480 } 481 482 /* We have the sum; we can divide to obtain the average values */ 483 for (i=0; i<NSCENAR; i++) 484 { 485 if (array_max[i] != -1) 486 { 487 Xavg[i] /= array_max[i]; 488 LnXavg[i] /= array_max[i]; 489 Yavg[i] /= array_max[i]; 490 LnYavg[i] /= array_max[i]; 491 } 492 } 493 494 #if VERBOSE > 1 495 output(" Found %d rows and %d columns\n", N, NSCENAR); 496 #endif 497 498 499 /* We will now alloc the array ... */ 500 Table = calloc(N, sizeof( struct row )); 501 if (Table == NULL) { UNRESOLVED(errno, "Unable to alloc space for results parsing"); } 502 503 /* ... and fill it */ 504 N = 0; 505 cur = measures; 506 507 while (cur->next != NULL) 508 { 509 cur = cur->next; 510 511 Table[N].X = (long) cur->nthreads; 512 Table[N].LnX = log((double) cur->nthreads); 513 for (i=0; i<NSCENAR; i++) 514 { 515 if (array_max[i] > N) 516 { 517 Table[N]._x[i] = Table[N].X - Xavg[i] ; 518 Table[N]._lnx[i] = Table[N].LnX - LnXavg[i]; 519 Table[N].Y[i] = cur->_data[i]; 520 Table[N]._y[i] = Table[N].Y[i] - Yavg[i] ; 521 Table[N].LnY[i] = log((double) cur->_data[i]); 522 Table[N]._lny[i] = Table[N].LnY[i] - LnYavg[i]; 523 } 524 } 525 526 N++; 527 } 528 529 /* We won't need the list anymore -- we'll work with the array which should be faster. */ 530 #if VERBOSE > 1 531 output(" Data was stored in an array.\n"); 532 #endif 533 534 /* We need to read the full array at least twice to compute all the error factors */ 535 536 /* In the first pass, we'll compute: 537 * -> r1 for each scenar. 538 * -> "a" factor for linear (0), power (1) and exponential (2) approximations -- with using the _d and _q vars. 539 */ 540 #if VERBOSE > 1 541 output("Starting first pass...\n"); 542 #endif 543 for (i=0; i<NSCENAR; i++) 544 { 545 for (r=0; r<array_max[i]; r++) 546 { 547 r1[i] += ((double)Table[r]._y[i] / array_max[i]) * (double)Table[r]._y[i]; 548 549 _q[0][i] += Table[r]._y[i] * Table[r]._x[i]; 550 _d[0][i] += Table[r]._x[i] * Table[r]._x[i]; 551 552 _q[1][i] += Table[r]._lny[i] * Table[r]._lnx[i]; 553 _d[1][i] += Table[r]._lnx[i] * Table[r]._lnx[i]; 554 555 _q[2][i] += Table[r]._lny[i] * Table[r]._x[i]; 556 _d[2][i] += Table[r]._x[i] * Table[r]._x[i]; 557 } 558 } 559 560 /* First pass is terminated; a2 = _q[0]/_d[0]; a3 = _q[1]/_d[1]; a4 = _q[2]/_d[2] */ 561 562 /* In the first pass, we'll compute: 563 * -> r2, r3, r4 for each scenar. 564 */ 565 566 #if VERBOSE > 1 567 output("Starting second pass...\n"); 568 #endif 569 for (i=0; i<NSCENAR; i++) 570 { 571 for (r=0; r<array_max[i]; r++) 572 { 573 /* r2 = avg((y - ax -b)²); t = (y - ax - b) = (y - yavg) - a (x - xavg); */ 574 t = ( Table[r]._y[i] - ((_q[0][i] * Table[r]._x[i]) / _d[0][i])); 575 r2[i] += t * t / array_max[i] ; 576 577 /* r3 = avg(( y - c.x^a) ²); 578 t = y - c * x ^ a 579 = y - log (LnYavg - (_q[1]/_d[1]) * LnXavg) * x ^ (_q[1]/_d[1]) 580 */ 581 t = ( Table[r].Y[i] 582 - ( logl ( LnYavg[i] - (_q[1][i] / _d[1][i] ) * LnXavg[i]) 583 * powl( Table[r].X, (_q[1][i] / _d[1][i] )) 584 ) ); 585 r3[i] += t * t / array_max[i] ; 586 587 /* r4 = avg(( y - exp(ax+b))²); 588 t = y - exp(ax+b) 589 = y - exp( _q[2]/_d[2] * x + ( LnYavg - (_q[2]/_d[2] * Xavg) )); 590 = y - exp( _q[2]/_d[2] * (x - Xavg) + LnYavg ); 591 */ 592 t = ( Table[r].Y[i] 593 - expl( ( _q[2][i] / _d[2][i] ) * Table[r]._x[i] + LnYavg[i] ) ); 594 r4[i] += t * t / array_max[i] ; 595 596 } 597 } 598 599 #if VERBOSE > 1 600 output("All computing terminated.\n"); 601 #endif 602 ret = 0; 603 for (i=0; i<NSCENAR; i++) 604 { 605 #if VERBOSE > 1 606 output("\nScenario: %s\n", scenarii[i].descr); 607 608 output(" # of data: %i\n", array_max[i]); 609 610 output(" Model: Y = k\n"); 611 output(" k = %g\n", Yavg[i]); 612 output(" Divergence %g\n", r1[i]); 613 614 output(" Model: Y = a * X + b\n"); 615 output(" a = %Lg\n", _q[0][i] / _d[0][i]); 616 output(" b = %Lg\n", Yavg[i] - ((_q[0][i] / _d[0][i]) * Xavg[i])); 617 output(" Divergence %g\n", r2[i]); 618 619 output(" Model: Y = c * X ^ a\n"); 620 output(" a = %Lg\n", _q[1][i] / _d[1][i]); 621 output(" c = %Lg\n", logl ( LnYavg[i] - (_q[1][i] / _d[1][i] ) * LnXavg[i])); 622 output(" Divergence %g\n", r2[i]); 623 624 output(" Model: Y = exp(a * X + b)\n"); 625 output(" a = %Lg\n", _q[2][i] / _d[2][i]); 626 output(" b = %Lg\n", LnYavg[i] - ((_q[2][i] / _d[2][i]) * Xavg[i])); 627 output(" Divergence %g\n", r2[i]); 628 #endif 629 630 if (array_max[i] != -1) 631 { 632 /* Compare r1 to other values, with some ponderations */ 633 if ((r1[i] > 1.1 * r2[i]) || (r1[i] > 1.2 * r3[i]) || (r1[i] > 1.3 * r4[i])) 634 ret++; 635 #if VERBOSE > 1 636 else 637 output(" Sanction: OK\n"); 638 #endif 639 } 640 } 641 642 /* We need to free the array */ 643 free(Table); 644 645 /* We're done */ 646 return ret; 647} 648 649