/* TODO: proper output */
/*
*
* Copyright (c) International Business Machines Corp., 2001
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
* the GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
/*
* FILE : pth_str03.c
* DESCRIPTION : create a tree of threads does calculations, and
* returns result to parent
* HISTORY:
* 05/l6/2001 Paul Larson (plars@us.ibm.com)
* -Ported
*
*/
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <stdint.h>
#include <sys/types.h>
#include "test.h"
#define MAXTHREADS 1000
/* Type definition */
struct kid_info {
long sum; /* sum of childrens indexes plus our own */
int index; /* our index into the array */
int status; /* return status of this thread */
int child_count; /* Count of children created */
int talk_count; /* Count of siblings that we talked to */
pthread_t *threads; /* dynamic array of thread id of kids */
pthread_mutex_t talk_mutex; /* mutex for the talk_count */
pthread_mutex_t child_mutex; /* mutex for the child_count */
pthread_cond_t talk_condvar; /* condition variable for talk_count */
pthread_cond_t child_condvar; /* condition variable for child_count */
struct kid_info **child_ptrs; /* dynamic array of ptrs to kids */
};
typedef struct kid_info c_info;
/* Global variables */
int depth = 3;
int breadth = 4;
int timeout = 30; /* minutes */
int cdepth; /* current depth */
int debug = 0;
c_info *child_info; /* pointer to info array */
int node_count; /* number of nodes created so far */
pthread_mutex_t node_mutex; /* mutex for the node_count */
pthread_cond_t node_condvar; /* condition variable for node_count */
pthread_attr_t attr; /* attributes for created threads */
int num_nodes(int, int);
int synchronize_children(c_info *);
void *doit(void *);
char *TCID = "pth_str03";
int TST_TOTAL = 1;
void testexit(int value)
{
if (value == 0)
tst_resm(TPASS, "Test passed");
else
tst_resm(TFAIL, "Test failed");
exit(value);
}
/*--------------------------------------------------------------------------------*
* parse_args
*
* Parse command line arguments. Any errors cause the program to exit
* at this point.
*--------------------------------------------------------------------------------*/
static void parse_args(int argc, char *argv[])
{
int opt, errflag = 0;
int bflag = 0, dflag = 0, tflag = 0;
while ((opt = getopt(argc, argv, "b:d:t:D?")) != EOF) {
switch (opt) {
case 'b':
if (bflag)
errflag++;
else {
bflag++;
breadth = atoi(optarg);
if (breadth <= 0)
errflag++;
}
break;
case 'd':
if (dflag)
errflag++;
else {
dflag++;
depth = atoi(optarg);
if (depth <= 0)
errflag++;
}
break;
case 't':
if (tflag)
errflag++;
else {
tflag++;
timeout = atoi(optarg);
if (timeout <= 0)
errflag++;
}
break;
case 'D':
debug = 1;
break;
case '?':
default:
errflag++;
break;
}
}
if (errflag) {
fprintf(stderr,
"usage: %s [-b <num>] [-d <num>] [-t <num>] [-D]",
argv[0]);
fprintf(stderr, "where:\n");
fprintf(stderr, "\t-b <num>\tbreadth of child nodes\n");
fprintf(stderr, "\t-d <num>\tdepth of child nodes\n");
fprintf(stderr,
"\t-t <num>\ttimeout for child communication (in minutes)\n");
fprintf(stderr, "\t-D\tdebug mode\n");
testexit(1);
}
}
/*--------------------------------------------------------------------------------*
* num_nodes
*
* Caculate the number of child nodes for a given breadth and depth tree.
*--------------------------------------------------------------------------------*/
int num_nodes(int b, int d)
{
int n, sum = 1, partial_exp = 1;
/*
* The total number of children = sum ( b ** n )
* n=0->d
* Since b ** 0 == 1, and it's hard to compute that kind of value
* in this simplistic loop, we start sum at 1 (above) to compensate
* and do the computations from 1->d below.
*/
for (n = 1; n <= d; n++) {
partial_exp *= b;
sum += partial_exp;
}
return (sum);
}
/*--------------------------------------------------------------------------------*
* synchronize_children
*
* Register the child with the parent and then wait for all of the children
* at the same level to register also. Return when everything is synched up.
*--------------------------------------------------------------------------------*/
int synchronize_children(c_info * parent)
{
int my_index, rc;
c_info *info_p;
struct timespec timer;
if (debug) {
printf("trying to lock node_mutex\n");
fflush(stdout);
}
/* Lock the node_count mutex to we can safely increment it. We
* will unlock it when we broadcast that all of our siblings have
* been created or when we block waiting for that broadcast. */
pthread_mutex_lock(&node_mutex);
my_index = node_count++;
tst_resm(TINFO, "thread %d started", my_index);
/* Get a pointer into the array of thread structures which will be "me". */
info_p = &child_info[my_index];
info_p->index = my_index;
info_p->sum = (long)my_index;
if (debug) {
printf("thread %d info_p=%p\n", my_index, info_p);
fflush(stdout);
}
/* Register with parent bumping the parent's child_count variable.
* Make sure we have exclusive access to that variable before we
* do the increment. */
if (debug) {
printf("thread %d locking child_mutex %p\n", my_index,
&parent->child_mutex);
fflush(stdout);
}
pthread_mutex_lock(&parent->child_mutex);
if (debug) {
printf("thread %d bumping child_count (currently %d)\n",
my_index, parent->child_count);
fflush(stdout);
}
parent->child_ptrs[parent->child_count++] = info_p;
if (debug) {
printf("thread %d unlocking child_mutex %p\n", my_index,
&parent->child_mutex);
fflush(stdout);
}
pthread_mutex_unlock(&parent->child_mutex);
if (debug) {
printf("thread %d node_count = %d\n", my_index, node_count);
printf("expecting %d nodes\n", num_nodes(breadth, cdepth));
fflush(stdout);
}
/* Have all the nodes at our level in the tree been created yet?
* If so, then send out a broadcast to wake everyone else up (to let
* them know they can now create their children (if they are not
* leaf nodes)). Otherwise, go to sleep waiting for the broadcast. */
if (node_count == num_nodes(breadth, cdepth)) {
/* Increase the current depth variable, as the tree is now
* fully one level taller. */
if (debug) {
printf("thread %d doing cdepth++ (%d)\n", my_index,
cdepth);
fflush(stdout);
}
cdepth++;
if (debug) {
printf("thread %d sending child_mutex broadcast\n",
my_index);
fflush(stdout);
}
/* Since all of our siblings have been created, this level of
* the tree is now allowed to continue its work, so wake up the
* rest of the siblings. */
pthread_cond_broadcast(&node_condvar);
} else {
/* In this case, not all of our siblings at this level of the
* tree have been created, so go to sleep and wait for the
* broadcast on node_condvar. */
if (debug) {
printf("thread %d waiting for siblings to register\n",
my_index);
fflush(stdout);
}
time(&timer.tv_sec);
timer.tv_sec += (unsigned long)timeout *60;
timer.tv_nsec = (unsigned long)0;
if ((rc = pthread_cond_timedwait(&node_condvar, &node_mutex,
&timer))) {
tst_resm(TINFO, "pthread_cond_timedwait (sync) %d: %s",
my_index, strerror(rc));
testexit(2);
}
if (debug) {
printf("thread %d is now unblocked\n", my_index);
fflush(stdout);
}
}
/* Unlock the node_mutex lock, as this thread is finished initializing. */
if (debug) {
printf("thread %d unlocking node_mutex\n", my_index);
fflush(stdout);
}
pthread_mutex_unlock(&node_mutex);
if (debug) {
printf("thread %d unlocked node_mutex\n", my_index);
fflush(stdout);
}
if (debug) {
printf("synchronize_children returning %d\n", my_index);
fflush(stdout);
}
return (my_index);
}
/*--------------------------------------------------------------------------------*
* doit
*
* Do it.
*--------------------------------------------------------------------------------*/
void *doit(void *param)
{
c_info *parent = (c_info *) param;
int rc, child, my_index;
void *status;
c_info *info_p;
struct timespec timer;
if (parent != NULL) {
/* Synchronize with our siblings so that all the children at
* a given level have been created before we allow those children
* to spawn new ones (or do anything else for that matter). */
if (debug) {
printf("non-root child calling synchronize_children\n");
fflush(stdout);
}
my_index = synchronize_children(parent);
if (debug) {
printf("non-root child has been assigned index %d\n",
my_index);
fflush(stdout);
}
} else {
/* The first thread has no one with which to synchronize, so
* set some initial values for things. */
if (debug) {
printf("root child\n");
fflush(stdout);
}
cdepth = 1;
my_index = 0;
node_count = 1;
}
/* Figure out our place in the pthread array. */
info_p = &child_info[my_index];
if (debug) {
printf("thread %d getting to heart of doit.\n", my_index);
printf("info_p=%p, cdepth=%d, depth=%d\n", info_p, cdepth,
depth);
fflush(stdout);
}
if (cdepth <= depth) {
/* Since the tree is not yet complete (it is not yet tall enough),
* we need to create another level of children. */
tst_resm(TINFO, "thread %d creating kids, cdepth=%d", my_index,
cdepth);
/* Create breadth children. */
for (child = 0; child < breadth; child++) {
if ((rc =
pthread_create(&(info_p->threads[child]), &attr,
doit, (void *)info_p))) {
tst_resm(TINFO, "pthread_create (doit): %s",
strerror(rc));
testexit(3);
} else {
if (debug) {
printf
("pthread_create made thread %p\n",
&(info_p->threads[child]));
fflush(stdout);
}
}
}
if (debug) {
printf("thread %d waits on kids, cdepth=%d\n", my_index,
cdepth);
fflush(stdout);
}
/* Wait for our children to finish before we exit ourselves. */
for (child = 0; child < breadth; child++) {
if (debug) {
printf("attempting join on thread %p\n",
&(info_p->threads[child]));
fflush(stdout);
}
if ((rc =
pthread_join((info_p->threads[child]), &status))) {
if (debug) {
printf
("join failed on thread %d, status addr=%p: %s\n",
my_index, status, strerror(rc));
fflush(stdout);
}
testexit(4);
} else {
if (debug) {
printf("thread %d joined child %d ok\n",
my_index, child);
fflush(stdout);
}
/* Add all childrens indexes to your index value */
info_p->sum += info_p->child_ptrs[child]->sum;
tst_resm(TINFO,
"thread %d adding child thread %d to sum = %ld",
my_index,
info_p->child_ptrs[child]->index,
(long int)info_p->sum);
}
}
} else {
/* This is the leaf node case. These children don't create
* any kids; they just talk amongst themselves. */
tst_resm(TINFO, "thread %d is a leaf node, depth=%d", my_index,
cdepth);
/* Talk to siblings (children of the same parent node). */
if (breadth > 1) {
for (child = 0; child < breadth; child++) {
/* Don't talk to yourself. */
if (parent->child_ptrs[child] != info_p) {
if (debug) {
printf
("thread %d locking talk_mutex\n",
my_index);
fflush(stdout);
}
pthread_mutex_lock(&
(parent->
child_ptrs[child]->
talk_mutex));
if (++parent->child_ptrs[child]->
talk_count == (breadth - 1)) {
if (debug) {
printf
("thread %d talk siblings\n",
my_index);
fflush(stdout);
}
if ((rc =
pthread_cond_broadcast
(&parent->
child_ptrs[child]->
talk_condvar))) {
tst_resm(TINFO,
"pthread_cond_broadcast: %s",
strerror(rc));
testexit(5);
}
}
if (debug) {
printf
("thread %d unlocking talk_mutex\n",
my_index);
fflush(stdout);
}
pthread_mutex_unlock(&
(parent->
child_ptrs
[child]->
talk_mutex));
}
}
/* Wait until the breadth - 1 siblings have contacted us. */
if (debug) {
printf("thread %d waiting for talk siblings\n",
my_index);
fflush(stdout);
}
pthread_mutex_lock(&info_p->talk_mutex);
if (info_p->talk_count < (breadth - 1)) {
time(&timer.tv_sec);
timer.tv_sec += (unsigned long)timeout *60;
timer.tv_nsec = (unsigned long)0;
if ((rc =
pthread_cond_timedwait(&info_p->
talk_condvar,
&info_p->talk_mutex,
&timer))) {
tst_resm(TINFO,
"pthread_cond_timedwait (leaf) %d: %s",
my_index, strerror(rc));
testexit(6);
}
}
pthread_mutex_unlock(&info_p->talk_mutex);
}
}
/* Our work is done. We're outta here. */
tst_resm(TINFO, "thread %d exiting, depth=%d, status=%d, addr=%p",
my_index, cdepth, info_p->status, info_p);
pthread_exit(0);
}
/*--------------------------------------------------------------------------------*
* main
*--------------------------------------------------------------------------------*/
int main(int argc, char *argv[])
{
int rc, ind, total;
pthread_t root_thread;
parse_args(argc, argv);
/* Initialize node mutex. */
if ((rc = pthread_mutex_init(&node_mutex, NULL))) {
tst_resm(TINFO, "pthread_mutex_init(node_mutex): %s",
strerror(rc));
testexit(7);
}
/* Initialize node condition variable. */
if ((rc = pthread_cond_init(&node_condvar, NULL))) {
tst_resm(TINFO, "pthread_cond_init(node_condvar): %s",
strerror(rc));
testexit(8);
}
/* Allocate pthread info structure array. */
if ((total = num_nodes(breadth, depth)) > MAXTHREADS) {
tst_resm(TINFO, "Can't create %d threads; max is %d.",
total, MAXTHREADS);
testexit(9);
}
tst_resm(TINFO, "Allocating %d nodes.", total);
if ((child_info = malloc(total * sizeof(c_info))) == NULL) {
perror("malloc child_info");
testexit(10);
}
memset(child_info, 0x00, total * sizeof(c_info));
if (debug) {
printf("Initializing array for %d children\n", total);
fflush(stdout);
}
/* Allocate array of pthreads descriptors and initialize variables. */
for (ind = 0; ind < total; ind++) {
if ((child_info[ind].threads = malloc(breadth * sizeof(pthread_t))) ==
NULL) {
perror("malloc threads");
testexit(11);
}
memset(child_info[ind].threads, 0x00,
breadth * sizeof(pthread_t));
if ((child_info[ind].child_ptrs = malloc(breadth * sizeof(c_info *))) == NULL) {
perror("malloc child_ptrs");
testexit(12);
}
memset(child_info[ind].child_ptrs, 0x00,
breadth * sizeof(c_info *));
if ((rc =
pthread_mutex_init(&child_info[ind].child_mutex, NULL))) {
tst_resm(TINFO, "pthread_mutex_init child_mutex: %s",
strerror(rc));
testexit(13);
}
if ((rc =
pthread_mutex_init(&child_info[ind].talk_mutex, NULL))) {
tst_resm(TINFO, "pthread_mutex_init talk_mutex: %s",
strerror(rc));
testexit(14);
}
if ((rc =
pthread_cond_init(&child_info[ind].child_condvar, NULL))) {
tst_resm(TINFO, "pthread_cond_init child_condvar: %s",
strerror(rc));
testexit(15);
}
if ((rc =
pthread_cond_init(&child_info[ind].talk_condvar, NULL))) {
tst_resm(TINFO, "pthread_cond_init talk_condvar: %s",
strerror(rc));
testexit(16);
}
if (debug) {
printf("Successfully initialized child %d.\n", ind);
fflush(stdout);
}
}
tst_resm(TINFO,
"Creating root thread attributes via pthread_attr_init.");
if ((rc = pthread_attr_init(&attr))) {
tst_resm(TINFO, "pthread_attr_init: %s", strerror(rc));
testexit(17);
}
/* Make sure that all the thread children we create have the
* PTHREAD_CREATE_JOINABLE attribute. If they don't, then the
* pthread_join call will sometimes fail and cause mass confusion. */
if ((rc = pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE))) {
tst_resm(TINFO, "pthread_attr_setdetachstate: %s",
strerror(rc));
testexit(18);
}
tst_resm(TINFO, "Creating root thread via pthread_create.");
if ((rc = pthread_create(&root_thread, &attr, doit, NULL))) {
tst_resm(TINFO, "pthread_create: %s", strerror(rc));
testexit(19);
}
if (debug) {
printf("Doing pthread_join.\n");
fflush(stdout);
}
/* Wait for the root child to exit. */
if ((rc = pthread_join(root_thread, NULL))) {
tst_resm(TINFO, "pthread_join: %s", strerror(rc));
testexit(20);
}
if (debug) {
printf("About to pthread_exit.\n");
fflush(stdout);
}
tst_resm(TINFO, "The sum of tree (breadth %d, depth %d) is %ld",
breadth, depth, child_info[0].sum);
testexit(0);
exit(0);
}