Line data Source code
1 : /*
2 : *
3 : * Copyright 2015, Google Inc.
4 : * All rights reserved.
5 : *
6 : * Redistribution and use in source and binary forms, with or without
7 : * modification, are permitted provided that the following conditions are
8 : * met:
9 : *
10 : * * Redistributions of source code must retain the above copyright
11 : * notice, this list of conditions and the following disclaimer.
12 : * * Redistributions in binary form must reproduce the above
13 : * copyright notice, this list of conditions and the following disclaimer
14 : * in the documentation and/or other materials provided with the
15 : * distribution.
16 : * * Neither the name of Google Inc. nor the names of its
17 : * contributors may be used to endorse or promote products derived from
18 : * this software without specific prior written permission.
19 : *
20 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 : * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 : * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 : * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 : * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 : * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 : * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 : * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 : * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 : * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 : * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 : *
32 : */
33 :
34 : #include "src/core/support/stack_lockfree.h"
35 :
36 : #include <stdlib.h>
37 :
38 : #include <grpc/support/alloc.h>
39 : #include <grpc/support/log.h>
40 : #include <grpc/support/sync.h>
41 : #include <grpc/support/thd.h>
42 : #include "test/core/util/test_config.h"
43 :
44 : /* max stack size supported */
45 : #define MAX_STACK_SIZE 65534
46 :
47 : #define MAX_THREADS 32
48 :
49 10 : static void test_serial_sized(size_t size) {
50 10 : gpr_stack_lockfree *stack = gpr_stack_lockfree_create(size);
51 : size_t i;
52 : size_t j;
53 :
54 : /* First try popping empty */
55 10 : GPR_ASSERT(gpr_stack_lockfree_pop(stack) == -1);
56 :
57 : /* Now add one item and check it */
58 10 : gpr_stack_lockfree_push(stack, 3);
59 10 : GPR_ASSERT(gpr_stack_lockfree_pop(stack) == 3);
60 10 : GPR_ASSERT(gpr_stack_lockfree_pop(stack) == -1);
61 :
62 : /* Now add repeatedly more items and check them */
63 125 : for (i = 1; i < size; i *= 2) {
64 131164 : for (j = 0; j <= i; j++) {
65 131049 : GPR_ASSERT(gpr_stack_lockfree_push(stack, (int)j) == (j == 0));
66 : }
67 131164 : for (j = 0; j <= i; j++) {
68 131049 : GPR_ASSERT(gpr_stack_lockfree_pop(stack) == (int)(i - j));
69 : }
70 115 : GPR_ASSERT(gpr_stack_lockfree_pop(stack) == -1);
71 : }
72 :
73 10 : gpr_stack_lockfree_destroy(stack);
74 10 : }
75 :
76 1 : static void test_serial() {
77 : size_t i;
78 10 : for (i = 128; i < MAX_STACK_SIZE; i *= 2) {
79 9 : test_serial_sized(i);
80 : }
81 1 : test_serial_sized(MAX_STACK_SIZE);
82 1 : }
83 :
84 : struct test_arg {
85 : gpr_stack_lockfree *stack;
86 : int stack_size;
87 : int nthreads;
88 : int rank;
89 : int sum;
90 : };
91 :
92 4775 : static void test_mt_body(void *v) {
93 4775 : struct test_arg *arg = (struct test_arg *)v;
94 : int lo, hi;
95 : int i;
96 : int res;
97 4775 : lo = arg->rank * arg->stack_size / arg->nthreads;
98 4775 : hi = (arg->rank + 1) * arg->stack_size / arg->nthreads;
99 4046876 : for (i = lo; i < hi; i++) {
100 4041916 : gpr_stack_lockfree_push(arg->stack, i);
101 4051949 : if ((res = gpr_stack_lockfree_pop(arg->stack)) != -1) {
102 4033704 : arg->sum += res;
103 : }
104 : }
105 10142 : while ((res = gpr_stack_lockfree_pop(arg->stack)) != -1) {
106 222 : arg->sum += res;
107 : }
108 4960 : }
109 :
110 310 : static void test_mt_sized(size_t size, int nth) {
111 : gpr_stack_lockfree *stack;
112 : struct test_arg args[MAX_THREADS];
113 : gpr_thd_id thds[MAX_THREADS];
114 : int sum;
115 : int i;
116 310 : gpr_thd_options options = gpr_thd_options_default();
117 :
118 310 : stack = gpr_stack_lockfree_create(size);
119 5270 : for (i = 0; i < nth; i++) {
120 4960 : args[i].stack = stack;
121 4960 : args[i].stack_size = (int)size;
122 4960 : args[i].nthreads = nth;
123 4960 : args[i].rank = i;
124 4960 : args[i].sum = 0;
125 : }
126 310 : gpr_thd_options_set_joinable(&options);
127 5270 : for (i = 0; i < nth; i++) {
128 4960 : GPR_ASSERT(gpr_thd_new(&thds[i], test_mt_body, &args[i], &options));
129 : }
130 310 : sum = 0;
131 5270 : for (i = 0; i < nth; i++) {
132 4960 : gpr_thd_join(thds[i]);
133 4960 : sum = sum + args[i].sum;
134 : }
135 310 : GPR_ASSERT((unsigned)sum == ((unsigned)size * (size - 1)) / 2);
136 310 : gpr_stack_lockfree_destroy(stack);
137 310 : }
138 :
139 1 : static void test_mt() {
140 : size_t size;
141 : int nth;
142 32 : for (nth = 1; nth < MAX_THREADS; nth++) {
143 310 : for (size = 128; size < MAX_STACK_SIZE; size *= 2) {
144 279 : test_mt_sized(size, nth);
145 : }
146 31 : test_mt_sized(MAX_STACK_SIZE, nth);
147 : }
148 1 : }
149 :
150 1 : int main(int argc, char **argv) {
151 1 : grpc_test_init(argc, argv);
152 1 : test_serial();
153 1 : test_mt();
154 1 : return 0;
155 : }
|