tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

stack.c (7042B)

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