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
42 int depth = 3;
43 int breadth = 4;
44 int timeout = 30; /* minutes */
45 int cdepth; /* current depth */
46 int debug = 0;
47
48 c_info *child_info; /* pointer to info array */
49 int node_count; /* number of nodes created so far */
50 pthread_mutex_t node_mutex; /* mutex for the node_count */
51 pthread_cond_t node_condvar; /* condition variable for node_count */
52 pthread_attr_t attr; /* attributes for created threads */
53
54 int num_nodes(int, int);
55 int synchronize_children(c_info *);
56 int doit(c_info *);
57
58 char *TCID = "pth_str01";
59 int TST_TOTAL = 1;
60
testexit(int value)61 void 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 */
parse_args(int argc,char * argv[])77 static 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 */
num_nodes(int b,int d)144 int 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 */
synchronize_children(c_info * parent)169 int 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 */
doit(c_info * parent)321 int 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 */
main(int argc,char * argv[])545 int 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