nsprpub/pr/tests/stack.c

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* This Source Code Form is subject to the terms of the Mozilla Public
   3  * License, v. 2.0. If a copy of the MPL was not distributed with this
   4  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   5
   6
   7 /*
   8  *
   9  * Test atomic stack operations
  10  *
  11  *              Two stacks are created and threads add data items (each containing
  12  *              one of the first n integers) to the first stack, remove data items
  13  *              from the first stack and add them to the second stack. The primordial
  14  *              thread compares the sum of the first n integers to the sum of the
  15  *              integers in the data items in the second stack. The test succeeds if
  16  *              they are equal.
  17  */
  18
  19 #include "nspr.h"
  20 #include "plgetopt.h"
  21
  22 typedef struct _DataRecord {
  23         PRInt32 data;
  24         PRStackElem     link;
  25 } DataRecord;
  26
  27 #define RECORD_LINK_PTR(lp) ((DataRecord*) ((char*) (lp) - offsetof(DataRecord,link)))
  28
  29 #define MAX_THREAD_CNT          100
  30 #define DEFAULT_THREAD_CNT      4
  31 #define DEFAULT_DATA_CNT        100
  32 #define DEFAULT_LOOP_CNT        10000
  33
  34 /*
  35  * sum of the first n numbers using the formula n*(n+1)/2
  36  */
  37 #define SUM_OF_NUMBERS(n) ((n & 1) ? (((n + 1)/2) * n) : ((n/2) * (n+1)))
  38
  39 typedef struct stack_data {
  40         PRStack         *list1;
  41         PRStack         *list2;
  42         PRInt32         initial_data_value;
  43         PRInt32         data_cnt;
  44         PRInt32         loops;
  45 } stack_data;
  46
  47 static void stackop(void *arg);
  48
  49 static int _debug_on;
  50
  51 PRFileDesc  *output;
  52 PRFileDesc  *errhandle;
  53
  54 int main(int argc, char **argv)
  55 {
  56 #if !(defined(SYMBIAN) && defined(__WINS__))
  57     PRInt32 rv, cnt, sum;
  58         DataRecord      *Item;
  59         PRStack         *list1, *list2;
  60         PRStackElem     *node;
  61         PRStatus rc;
  62
  63         PRInt32 thread_cnt = DEFAULT_THREAD_CNT;
  64         PRInt32 data_cnt = DEFAULT_DATA_CNT;
  65         PRInt32 loops = DEFAULT_LOOP_CNT;
  66         PRThread **threads;
  67         stack_data *thread_args;
  68
  69         PLOptStatus os;
  70         PLOptState *opt = PL_CreateOptState(argc, argv, "dt:c:l:");
  71
  72         while (PL_OPT_EOL != (os = PL_GetNextOpt(opt)))
  73     {
  74                 if (PL_OPT_BAD == os) continue;
  75         switch (opt->option)
  76         {
  77         case 'd':  /* debug mode */
  78                         _debug_on = 1;
  79             break;
  80         case 't':  /* thread count */
  81             thread_cnt = atoi(opt->value);
  82             break;
  83         case 'c':  /* data count */
  84             data_cnt = atoi(opt->value);
  85             break;
  86         case 'l':  /* loop count */
  87             loops = atoi(opt->value);
  88             break;
  89          default:
  90             break;
  91         }
  92     }
  93         PL_DestroyOptState(opt);
  94
  95         PR_SetConcurrency(4);
  96
  97     output = PR_GetSpecialFD(PR_StandardOutput);
  98     errhandle = PR_GetSpecialFD(PR_StandardError);
  99         list1 = PR_CreateStack("Stack_1");
 100         if (list1 == NULL) {
 101                 PR_fprintf(errhandle, "PR_CreateStack failed - error %d\n",
 102                                                                 PR_GetError());
 103                 return 1;
 104         }
 105
 106         list2 = PR_CreateStack("Stack_2");
 107         if (list2 == NULL) {
 108                 PR_fprintf(errhandle, "PR_CreateStack failed - error %d\n",
 109                                                                 PR_GetError());
 110                 return 1;
 111         }
 112
 113
 114         threads = (PRThread**) PR_CALLOC(sizeof(PRThread*) * thread_cnt);
 115         thread_args = (stack_data *) PR_CALLOC(sizeof(stack_data) * thread_cnt);
 116
 117         if (_debug_on)
 118                 PR_fprintf(output,"%s: thread_cnt = %d data_cnt = %d\n", argv[0],
 119                                                         thread_cnt, data_cnt);
 120         for(cnt = 0; cnt < thread_cnt; cnt++) {
 121                 PRThreadScope scope;
 122
 123                 thread_args[cnt].list1 = list1;
 124                 thread_args[cnt].list2 = list2;
 125                 thread_args[cnt].loops = loops;
 126                 thread_args[cnt].data_cnt = data_cnt;
 127                 thread_args[cnt].initial_data_value = 1 + cnt * data_cnt;
 128
 129                 if (cnt & 1)
 130                         scope = PR_GLOBAL_THREAD;
 131                 else
 132                         scope = PR_LOCAL_THREAD;
 133
 134
 135                 threads[cnt] = PR_CreateThread(PR_USER_THREAD,
 136                                                   stackop, &thread_args[cnt],
 137                                                   PR_PRIORITY_NORMAL,
 138                                                   scope,
 139                                                   PR_JOINABLE_THREAD,
 140                                                   0);
 141                 if (threads[cnt] == NULL) {
 142                         PR_fprintf(errhandle, "PR_CreateThread failed - error %d\n",
 143                                                                 PR_GetError());
 144                         PR_ProcessExit(2);
 145                 }
 146                 if (_debug_on)
 147                         PR_fprintf(output,"%s: created thread = 0x%x\n", argv[0],
 148                                                                                 threads[cnt]);
 149         }
 150
 151         for(cnt = 0; cnt < thread_cnt; cnt++) {
 152         rc = PR_JoinThread(threads[cnt]);
 153                 PR_ASSERT(rc == PR_SUCCESS);
 154         }
 155
 156         node = PR_StackPop(list1);
 157         /*
 158          * list1 should be empty
 159          */
 160         if (node != NULL) {
 161                 PR_fprintf(errhandle, "Error - Stack 1 not empty\n");
 162                 PR_ASSERT(node == NULL);
 163                 PR_ProcessExit(4);
 164         }
 165
 166         cnt = data_cnt * thread_cnt;
 167         sum = 0;
 168         while (cnt-- > 0) {
 169                 node = PR_StackPop(list2);
 170                 /*
 171                  * There should be at least 'cnt' number of records
 172                  */
 173                 if (node == NULL) {
 174                         PR_fprintf(errhandle, "Error - PR_StackPop returned NULL\n");
 175                         PR_ProcessExit(3);
 176                 }
 177                 Item = RECORD_LINK_PTR(node);
 178                 sum += Item->data;
 179         }
 180         node = PR_StackPop(list2);
 181         /*
 182          * there should be exactly 'cnt' number of records
 183          */
 184         if (node != NULL) {
 185                 PR_fprintf(errhandle, "Error - Stack 2 not empty\n");
 186                 PR_ASSERT(node == NULL);
 187                 PR_ProcessExit(4);
 188         }
 189         PR_DELETE(threads);
 190         PR_DELETE(thread_args);
 191
 192         PR_DestroyStack(list1);
 193         PR_DestroyStack(list2);
 194
 195         if (sum == SUM_OF_NUMBERS(data_cnt * thread_cnt)) {
 196                 PR_fprintf(output, "%s successful\n", argv[0]);
 197                 PR_fprintf(output, "\t\tsum = 0x%x, expected = 0x%x\n", sum,
 198                                                         SUM_OF_NUMBERS(thread_cnt * data_cnt));
 199                 return 0;
 200         } else {
 201                 PR_fprintf(output, "%s failed: sum = 0x%x, expected = 0x%x\n",
 202                                                         argv[0], sum,
 203                                                                 SUM_OF_NUMBERS(data_cnt * thread_cnt));
 204                 return 2;
 205         }
 206 #endif
 207 }
 208
 209 static void stackop(void *thread_arg)
 210 {
 211     PRInt32 val, cnt, index, loops;
 212         DataRecord      *Items, *Item;
 213         PRStack         *list1, *list2;
 214         PRStackElem     *node;
 215         stack_data *arg = (stack_data *) thread_arg;
 216
 217         val = arg->initial_data_value;
 218         cnt = arg->data_cnt;
 219         loops = arg->loops;
 220         list1 = arg->list1;
 221         list2 = arg->list2;
 222
 223         /*
 224          * allocate memory for the data records
 225          */
 226         Items = (DataRecord *) PR_CALLOC(sizeof(DataRecord) * cnt);
 227         PR_ASSERT(Items != NULL);
 228         index = 0;
 229
 230         if (_debug_on)
 231                 PR_fprintf(output,
 232                 "Thread[0x%x] init_val = %d cnt = %d data1 = 0x%x datan = 0x%x\n",
 233                                 PR_GetCurrentThread(), val, cnt, &Items[0], &Items[cnt-1]);
 234
 235
 236         /*
 237          * add the data records to list1
 238          */
 239         while (cnt-- > 0) {
 240                 Items[index].data = val++;
 241                 PR_StackPush(list1, &Items[index].link);
 242                 index++;
 243         }
 244
 245         /*
 246          * pop data records from list1 and add them back to list1
 247          * generates contention for the stack accesses
 248          */
 249         while (loops-- > 0) {
 250                 cnt = arg->data_cnt;
 251                 while (cnt-- > 0) {
 252                         node = PR_StackPop(list1);
 253                         if (node == NULL) {
 254                                 PR_fprintf(errhandle, "Error - PR_StackPop returned NULL\n");
 255                                 PR_ASSERT(node != NULL);
 256                                 PR_ProcessExit(3);
 257                         }
 258                         PR_StackPush(list1, node);
 259                 }
 260         }
 261         /*
 262          * remove the data records from list1 and add them to list2
 263          */
 264         cnt = arg->data_cnt;
 265         while (cnt-- > 0) {
 266                 node = PR_StackPop(list1);
 267                 if (node == NULL) {
 268                         PR_fprintf(errhandle, "Error - PR_StackPop returned NULL\n");
 269                         PR_ASSERT(node != NULL);
 270                         PR_ProcessExit(3);
 271                 }
 272                 PR_StackPush(list2, node);
 273         }
 274         if (_debug_on)
 275                 PR_fprintf(output,
 276                 "Thread[0x%x] init_val = %d cnt = %d exiting\n",
 277                                 PR_GetCurrentThread(), val, cnt);
 278
 279 }
 280