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