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@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
testexit(int value)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 *--------------------------------------------------------------------------------*/
parse_args(int argc,char * argv[])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 *--------------------------------------------------------------------------------*/
num_nodes(int b,int d)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 *--------------------------------------------------------------------------------*/
synchronize_children(c_info * parent)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 *--------------------------------------------------------------------------------*/
doit(void * param)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 *--------------------------------------------------------------------------------*/
main(int argc,char * argv[])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