1 /* TODO: proper output */ 2 3 /* 4 * 5 * Copyright (c) International Business Machines Corp., 2001 6 * 7 * This program is free software; you can redistribute it and/or modify 8 * it under the terms of the GNU General Public License as published by 9 * the Free Software Foundation; either version 2 of the License, or 10 * (at your option) any later version. 11 * 12 * This program is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See 15 * the GNU General Public License for more details. 16 * 17 * You should have received a copy of the GNU General Public License 18 * along with this program; if not, write to the Free Software 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 20 */ 21 22 /* 23 * FILE : pth_str03.c 24 * DESCRIPTION : create a tree of threads does calculations, and 25 * returns result to parent 26 * HISTORY: 27 * 05/l6/2001 Paul Larson (plars (at) us.ibm.com) 28 * -Ported 29 * 30 */ 31 32 #include <pthread.h> 33 #include <stdio.h> 34 #include <unistd.h> 35 #include <stdlib.h> 36 #include <string.h> 37 #include <errno.h> 38 #include <stdint.h> 39 #include <sys/types.h> 40 #include "test.h" 41 42 #define MAXTHREADS 1000 43 44 /* Type definition */ 45 struct kid_info { 46 long sum; /* sum of childrens indexes plus our own */ 47 int index; /* our index into the array */ 48 int status; /* return status of this thread */ 49 int child_count; /* Count of children created */ 50 int talk_count; /* Count of siblings that we talked to */ 51 pthread_t *threads; /* dynamic array of thread id of kids */ 52 pthread_mutex_t talk_mutex; /* mutex for the talk_count */ 53 pthread_mutex_t child_mutex; /* mutex for the child_count */ 54 pthread_cond_t talk_condvar; /* condition variable for talk_count */ 55 pthread_cond_t child_condvar; /* condition variable for child_count */ 56 struct kid_info **child_ptrs; /* dynamic array of ptrs to kids */ 57 }; 58 typedef struct kid_info c_info; 59 60 /* Global variables */ 61 int depth = 3; 62 int breadth = 4; 63 int timeout = 30; /* minutes */ 64 int cdepth; /* current depth */ 65 int debug = 0; 66 67 c_info *child_info; /* pointer to info array */ 68 int node_count; /* number of nodes created so far */ 69 pthread_mutex_t node_mutex; /* mutex for the node_count */ 70 pthread_cond_t node_condvar; /* condition variable for node_count */ 71 pthread_attr_t attr; /* attributes for created threads */ 72 73 int num_nodes(int, int); 74 int synchronize_children(c_info *); 75 void *doit(void *); 76 77 char *TCID = "pth_str03"; 78 int TST_TOTAL = 1; 79 80 void testexit(int value) 81 { 82 if (value == 0) 83 tst_resm(TPASS, "Test passed"); 84 else 85 tst_resm(TFAIL, "Test failed"); 86 87 exit(value); 88 } 89 90 /*--------------------------------------------------------------------------------* 91 * parse_args 92 * 93 * Parse command line arguments. Any errors cause the program to exit 94 * at this point. 95 *--------------------------------------------------------------------------------*/ 96 static void parse_args(int argc, char *argv[]) 97 { 98 int opt, errflag = 0; 99 int bflag = 0, dflag = 0, tflag = 0; 100 101 while ((opt = getopt(argc, argv, "b:d:t:D?")) != EOF) { 102 switch (opt) { 103 case 'b': 104 if (bflag) 105 errflag++; 106 else { 107 bflag++; 108 breadth = atoi(optarg); 109 if (breadth <= 0) 110 errflag++; 111 } 112 break; 113 case 'd': 114 if (dflag) 115 errflag++; 116 else { 117 dflag++; 118 depth = atoi(optarg); 119 if (depth <= 0) 120 errflag++; 121 } 122 break; 123 case 't': 124 if (tflag) 125 errflag++; 126 else { 127 tflag++; 128 timeout = atoi(optarg); 129 if (timeout <= 0) 130 errflag++; 131 } 132 break; 133 case 'D': 134 debug = 1; 135 break; 136 case '?': 137 default: 138 errflag++; 139 break; 140 } 141 } 142 143 if (errflag) { 144 fprintf(stderr, 145 "usage: %s [-b <num>] [-d <num>] [-t <num>] [-D]", 146 argv[0]); 147 fprintf(stderr, "where:\n"); 148 fprintf(stderr, "\t-b <num>\tbreadth of child nodes\n"); 149 fprintf(stderr, "\t-d <num>\tdepth of child nodes\n"); 150 fprintf(stderr, 151 "\t-t <num>\ttimeout for child communication (in minutes)\n"); 152 fprintf(stderr, "\t-D\tdebug mode\n"); 153 testexit(1); 154 } 155 156 } 157 158 /*--------------------------------------------------------------------------------* 159 * num_nodes 160 * 161 * Caculate the number of child nodes for a given breadth and depth tree. 162 *--------------------------------------------------------------------------------*/ 163 int num_nodes(int b, int d) 164 { 165 int n, sum = 1, partial_exp = 1; 166 167 /* 168 * The total number of children = sum ( b ** n ) 169 * n=0->d 170 * Since b ** 0 == 1, and it's hard to compute that kind of value 171 * in this simplistic loop, we start sum at 1 (above) to compensate 172 * and do the computations from 1->d below. 173 */ 174 for (n = 1; n <= d; n++) { 175 partial_exp *= b; 176 sum += partial_exp; 177 } 178 179 return (sum); 180 } 181 182 /*--------------------------------------------------------------------------------* 183 * synchronize_children 184 * 185 * Register the child with the parent and then wait for all of the children 186 * at the same level to register also. Return when everything is synched up. 187 *--------------------------------------------------------------------------------*/ 188 int synchronize_children(c_info * parent) 189 { 190 int my_index, rc; 191 c_info *info_p; 192 struct timespec timer; 193 194 if (debug) { 195 printf("trying to lock node_mutex\n"); 196 fflush(stdout); 197 } 198 199 /* Lock the node_count mutex to we can safely increment it. We 200 * will unlock it when we broadcast that all of our siblings have 201 * been created or when we block waiting for that broadcast. */ 202 pthread_mutex_lock(&node_mutex); 203 my_index = node_count++; 204 205 tst_resm(TINFO, "thread %d started", my_index); 206 207 /* Get a pointer into the array of thread structures which will be "me". */ 208 info_p = &child_info[my_index]; 209 info_p->index = my_index; 210 info_p->sum = (long)my_index; 211 212 if (debug) { 213 printf("thread %d info_p=%p\n", my_index, info_p); 214 fflush(stdout); 215 } 216 217 /* Register with parent bumping the parent's child_count variable. 218 * Make sure we have exclusive access to that variable before we 219 * do the increment. */ 220 if (debug) { 221 printf("thread %d locking child_mutex %p\n", my_index, 222 &parent->child_mutex); 223 fflush(stdout); 224 } 225 pthread_mutex_lock(&parent->child_mutex); 226 if (debug) { 227 printf("thread %d bumping child_count (currently %d)\n", 228 my_index, parent->child_count); 229 fflush(stdout); 230 } 231 parent->child_ptrs[parent->child_count++] = info_p; 232 if (debug) { 233 printf("thread %d unlocking child_mutex %p\n", my_index, 234 &parent->child_mutex); 235 fflush(stdout); 236 } 237 pthread_mutex_unlock(&parent->child_mutex); 238 239 if (debug) { 240 printf("thread %d node_count = %d\n", my_index, node_count); 241 printf("expecting %d nodes\n", num_nodes(breadth, cdepth)); 242 fflush(stdout); 243 } 244 245 /* Have all the nodes at our level in the tree been created yet? 246 * If so, then send out a broadcast to wake everyone else up (to let 247 * them know they can now create their children (if they are not 248 * leaf nodes)). Otherwise, go to sleep waiting for the broadcast. */ 249 if (node_count == num_nodes(breadth, cdepth)) { 250 251 /* Increase the current depth variable, as the tree is now 252 * fully one level taller. */ 253 if (debug) { 254 printf("thread %d doing cdepth++ (%d)\n", my_index, 255 cdepth); 256 fflush(stdout); 257 } 258 cdepth++; 259 260 if (debug) { 261 printf("thread %d sending child_mutex broadcast\n", 262 my_index); 263 fflush(stdout); 264 } 265 266 /* Since all of our siblings have been created, this level of 267 * the tree is now allowed to continue its work, so wake up the 268 * rest of the siblings. */ 269 pthread_cond_broadcast(&node_condvar); 270 271 } else { 272 273 /* In this case, not all of our siblings at this level of the 274 * tree have been created, so go to sleep and wait for the 275 * broadcast on node_condvar. */ 276 if (debug) { 277 printf("thread %d waiting for siblings to register\n", 278 my_index); 279 fflush(stdout); 280 } 281 time(&timer.tv_sec); 282 timer.tv_sec += (unsigned long)timeout *60; 283 timer.tv_nsec = (unsigned long)0; 284 if ((rc = pthread_cond_timedwait(&node_condvar, &node_mutex, 285 &timer))) { 286 tst_resm(TINFO, "pthread_cond_timedwait (sync) %d: %s", 287 my_index, strerror(rc)); 288 testexit(2); 289 } 290 291 if (debug) { 292 printf("thread %d is now unblocked\n", my_index); 293 fflush(stdout); 294 } 295 296 } 297 298 /* Unlock the node_mutex lock, as this thread is finished initializing. */ 299 if (debug) { 300 printf("thread %d unlocking node_mutex\n", my_index); 301 fflush(stdout); 302 } 303 pthread_mutex_unlock(&node_mutex); 304 if (debug) { 305 printf("thread %d unlocked node_mutex\n", my_index); 306 fflush(stdout); 307 } 308 309 if (debug) { 310 printf("synchronize_children returning %d\n", my_index); 311 fflush(stdout); 312 } 313 314 return (my_index); 315 } 316 317 /*--------------------------------------------------------------------------------* 318 * doit 319 * 320 * Do it. 321 *--------------------------------------------------------------------------------*/ 322 void *doit(void *param) 323 { 324 c_info *parent = (c_info *) param; 325 int rc, child, my_index; 326 void *status; 327 c_info *info_p; 328 struct timespec timer; 329 330 if (parent != NULL) { 331 /* Synchronize with our siblings so that all the children at 332 * a given level have been created before we allow those children 333 * to spawn new ones (or do anything else for that matter). */ 334 if (debug) { 335 printf("non-root child calling synchronize_children\n"); 336 fflush(stdout); 337 } 338 my_index = synchronize_children(parent); 339 if (debug) { 340 printf("non-root child has been assigned index %d\n", 341 my_index); 342 fflush(stdout); 343 } 344 } else { 345 /* The first thread has no one with which to synchronize, so 346 * set some initial values for things. */ 347 if (debug) { 348 printf("root child\n"); 349 fflush(stdout); 350 } 351 cdepth = 1; 352 my_index = 0; 353 node_count = 1; 354 } 355 356 /* Figure out our place in the pthread array. */ 357 info_p = &child_info[my_index]; 358 359 if (debug) { 360 printf("thread %d getting to heart of doit.\n", my_index); 361 printf("info_p=%p, cdepth=%d, depth=%d\n", info_p, cdepth, 362 depth); 363 fflush(stdout); 364 } 365 366 if (cdepth <= depth) { 367 /* Since the tree is not yet complete (it is not yet tall enough), 368 * we need to create another level of children. */ 369 370 tst_resm(TINFO, "thread %d creating kids, cdepth=%d", my_index, 371 cdepth); 372 373 /* Create breadth children. */ 374 for (child = 0; child < breadth; child++) { 375 if ((rc = 376 pthread_create(&(info_p->threads[child]), &attr, 377 doit, (void *)info_p))) { 378 tst_resm(TINFO, "pthread_create (doit): %s", 379 strerror(rc)); 380 testexit(3); 381 } else { 382 if (debug) { 383 printf 384 ("pthread_create made thread %p\n", 385 &(info_p->threads[child])); 386 fflush(stdout); 387 } 388 } 389 } 390 391 if (debug) { 392 printf("thread %d waits on kids, cdepth=%d\n", my_index, 393 cdepth); 394 fflush(stdout); 395 } 396 397 /* Wait for our children to finish before we exit ourselves. */ 398 for (child = 0; child < breadth; child++) { 399 if (debug) { 400 printf("attempting join on thread %p\n", 401 &(info_p->threads[child])); 402 fflush(stdout); 403 } 404 if ((rc = 405 pthread_join((info_p->threads[child]), &status))) { 406 if (debug) { 407 printf 408 ("join failed on thread %d, status addr=%p: %s\n", 409 my_index, status, strerror(rc)); 410 fflush(stdout); 411 } 412 testexit(4); 413 } else { 414 if (debug) { 415 printf("thread %d joined child %d ok\n", 416 my_index, child); 417 fflush(stdout); 418 } 419 420 /* Add all childrens indexes to your index value */ 421 info_p->sum += info_p->child_ptrs[child]->sum; 422 tst_resm(TINFO, 423 "thread %d adding child thread %d to sum = %ld", 424 my_index, 425 info_p->child_ptrs[child]->index, 426 (long int)info_p->sum); 427 } 428 } 429 430 } else { 431 432 /* This is the leaf node case. These children don't create 433 * any kids; they just talk amongst themselves. */ 434 tst_resm(TINFO, "thread %d is a leaf node, depth=%d", my_index, 435 cdepth); 436 437 /* Talk to siblings (children of the same parent node). */ 438 if (breadth > 1) { 439 440 for (child = 0; child < breadth; child++) { 441 /* Don't talk to yourself. */ 442 if (parent->child_ptrs[child] != info_p) { 443 if (debug) { 444 printf 445 ("thread %d locking talk_mutex\n", 446 my_index); 447 fflush(stdout); 448 } 449 pthread_mutex_lock(& 450 (parent-> 451 child_ptrs[child]-> 452 talk_mutex)); 453 if (++parent->child_ptrs[child]-> 454 talk_count == (breadth - 1)) { 455 if (debug) { 456 printf 457 ("thread %d talk siblings\n", 458 my_index); 459 fflush(stdout); 460 } 461 if ((rc = 462 pthread_cond_broadcast 463 (&parent-> 464 child_ptrs[child]-> 465 talk_condvar))) { 466 tst_resm(TINFO, 467 "pthread_cond_broadcast: %s", 468 strerror(rc)); 469 testexit(5); 470 } 471 } 472 if (debug) { 473 printf 474 ("thread %d unlocking talk_mutex\n", 475 my_index); 476 fflush(stdout); 477 } 478 pthread_mutex_unlock(& 479 (parent-> 480 child_ptrs 481 [child]-> 482 talk_mutex)); 483 } 484 } 485 486 /* Wait until the breadth - 1 siblings have contacted us. */ 487 if (debug) { 488 printf("thread %d waiting for talk siblings\n", 489 my_index); 490 fflush(stdout); 491 } 492 493 pthread_mutex_lock(&info_p->talk_mutex); 494 if (info_p->talk_count < (breadth - 1)) { 495 time(&timer.tv_sec); 496 timer.tv_sec += (unsigned long)timeout *60; 497 timer.tv_nsec = (unsigned long)0; 498 if ((rc = 499 pthread_cond_timedwait(&info_p-> 500 talk_condvar, 501 &info_p->talk_mutex, 502 &timer))) { 503 tst_resm(TINFO, 504 "pthread_cond_timedwait (leaf) %d: %s", 505 my_index, strerror(rc)); 506 testexit(6); 507 } 508 } 509 pthread_mutex_unlock(&info_p->talk_mutex); 510 511 } 512 513 } 514 515 /* Our work is done. We're outta here. */ 516 tst_resm(TINFO, "thread %d exiting, depth=%d, status=%d, addr=%p", 517 my_index, cdepth, info_p->status, info_p); 518 519 pthread_exit(0); 520 } 521 522 /*--------------------------------------------------------------------------------* 523 * main 524 *--------------------------------------------------------------------------------*/ 525 int main(int argc, char *argv[]) 526 { 527 int rc, ind, total; 528 pthread_t root_thread; 529 530 parse_args(argc, argv); 531 532 /* Initialize node mutex. */ 533 if ((rc = pthread_mutex_init(&node_mutex, NULL))) { 534 tst_resm(TINFO, "pthread_mutex_init(node_mutex): %s", 535 strerror(rc)); 536 testexit(7); 537 } 538 539 /* Initialize node condition variable. */ 540 if ((rc = pthread_cond_init(&node_condvar, NULL))) { 541 tst_resm(TINFO, "pthread_cond_init(node_condvar): %s", 542 strerror(rc)); 543 testexit(8); 544 } 545 546 /* Allocate pthread info structure array. */ 547 if ((total = num_nodes(breadth, depth)) > MAXTHREADS) { 548 tst_resm(TINFO, "Can't create %d threads; max is %d.", 549 total, MAXTHREADS); 550 testexit(9); 551 } 552 tst_resm(TINFO, "Allocating %d nodes.", total); 553 if ((child_info = malloc(total * sizeof(c_info))) == NULL) { 554 perror("malloc child_info"); 555 testexit(10); 556 } 557 memset(child_info, 0x00, total * sizeof(c_info)); 558 559 if (debug) { 560 printf("Initializing array for %d children\n", total); 561 fflush(stdout); 562 } 563 564 /* Allocate array of pthreads descriptors and initialize variables. */ 565 for (ind = 0; ind < total; ind++) { 566 567 if ((child_info[ind].threads = malloc(breadth * sizeof(pthread_t))) == 568 NULL) { 569 perror("malloc threads"); 570 testexit(11); 571 } 572 memset(child_info[ind].threads, 0x00, 573 breadth * sizeof(pthread_t)); 574 575 if ((child_info[ind].child_ptrs = malloc(breadth * sizeof(c_info *))) == NULL) { 576 perror("malloc child_ptrs"); 577 testexit(12); 578 } 579 memset(child_info[ind].child_ptrs, 0x00, 580 breadth * sizeof(c_info *)); 581 582 if ((rc = 583 pthread_mutex_init(&child_info[ind].child_mutex, NULL))) { 584 tst_resm(TINFO, "pthread_mutex_init child_mutex: %s", 585 strerror(rc)); 586 testexit(13); 587 } 588 589 if ((rc = 590 pthread_mutex_init(&child_info[ind].talk_mutex, NULL))) { 591 tst_resm(TINFO, "pthread_mutex_init talk_mutex: %s", 592 strerror(rc)); 593 testexit(14); 594 } 595 596 if ((rc = 597 pthread_cond_init(&child_info[ind].child_condvar, NULL))) { 598 tst_resm(TINFO, "pthread_cond_init child_condvar: %s", 599 strerror(rc)); 600 testexit(15); 601 } 602 603 if ((rc = 604 pthread_cond_init(&child_info[ind].talk_condvar, NULL))) { 605 tst_resm(TINFO, "pthread_cond_init talk_condvar: %s", 606 strerror(rc)); 607 testexit(16); 608 } 609 610 if (debug) { 611 printf("Successfully initialized child %d.\n", ind); 612 fflush(stdout); 613 } 614 615 } 616 617 tst_resm(TINFO, 618 "Creating root thread attributes via pthread_attr_init."); 619 620 if ((rc = pthread_attr_init(&attr))) { 621 tst_resm(TINFO, "pthread_attr_init: %s", strerror(rc)); 622 testexit(17); 623 } 624 625 /* Make sure that all the thread children we create have the 626 * PTHREAD_CREATE_JOINABLE attribute. If they don't, then the 627 * pthread_join call will sometimes fail and cause mass confusion. */ 628 if ((rc = pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE))) { 629 tst_resm(TINFO, "pthread_attr_setdetachstate: %s", 630 strerror(rc)); 631 testexit(18); 632 } 633 634 tst_resm(TINFO, "Creating root thread via pthread_create."); 635 636 if ((rc = pthread_create(&root_thread, &attr, doit, NULL))) { 637 tst_resm(TINFO, "pthread_create: %s", strerror(rc)); 638 testexit(19); 639 } 640 641 if (debug) { 642 printf("Doing pthread_join.\n"); 643 fflush(stdout); 644 } 645 646 /* Wait for the root child to exit. */ 647 if ((rc = pthread_join(root_thread, NULL))) { 648 tst_resm(TINFO, "pthread_join: %s", strerror(rc)); 649 testexit(20); 650 } 651 652 if (debug) { 653 printf("About to pthread_exit.\n"); 654 fflush(stdout); 655 } 656 657 tst_resm(TINFO, "The sum of tree (breadth %d, depth %d) is %ld", 658 breadth, depth, child_info[0].sum); 659 testexit(0); 660 661 exit(0); 662 } 663