nsprpub/pr/tests/stack.c

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