1 /*
2 * Copyright (C) 2016-2021 Canonical, Ltd.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17 *
18 * This code is a complete clean re-write of the stress tool by
19 * Colin Ian King <colin.king@canonical.com> and attempts to be
20 * backwardly compatible with the stress tool by Amos Waterland
21 * <apw@rossby.metr.ou.edu> but has more stress tests and more
22 * functionality.
23 *
24 */
25 #include "stress-ng.h"
26
27 #if defined(HAVE_LIB_BSD)
28 static volatile bool do_jmp = true;
29 static sigjmp_buf jmp_env;
30 #endif
31
32 static const stress_help_t help[] = {
33 { NULL, "heapsort N", "start N workers heap sorting 32 bit random integers" },
34 { NULL, "heapsort-ops N", "stop after N heap sort bogo operations" },
35 { NULL, "heapsort-size N", "number of 32 bit integers to sort" },
36 { NULL, NULL, NULL }
37 };
38
39 /*
40 * stress_set_heapsort_size()
41 * set heapsort size
42 */
stress_set_heapsort_size(const char * opt)43 static int stress_set_heapsort_size(const char *opt)
44 {
45 uint64_t heapsort_size;
46
47 heapsort_size = stress_get_uint64(opt);
48 stress_check_range("heapsort-size", heapsort_size,
49 MIN_HEAPSORT_SIZE, MAX_HEAPSORT_SIZE);
50 return stress_set_setting("heapsort-size", TYPE_ID_UINT64, &heapsort_size);
51 }
52
53 static const stress_opt_set_func_t opt_set_funcs[] = {
54 { OPT_heapsort_integers, stress_set_heapsort_size },
55 { 0, NULL }
56 };
57
58 #if defined(HAVE_LIB_BSD)
59
60 /*
61 * stress_heapsort_handler()
62 * SIGALRM generic handler
63 */
stress_heapsort_handler(int signum)64 static void MLOCKED_TEXT stress_heapsort_handler(int signum)
65 {
66 (void)signum;
67
68 if (do_jmp) {
69 do_jmp = false;
70 siglongjmp(jmp_env, 1); /* Ugly, bounce back */
71 }
72 }
73
74 /*
75 * stress_heapsort_cmp_1()
76 * heapsort comparison - sort on int32 values
77 */
stress_heapsort_cmp_1(const void * p1,const void * p2)78 static int stress_heapsort_cmp_1(const void *p1, const void *p2)
79 {
80 const int32_t *i1 = (const int32_t *)p1;
81 const int32_t *i2 = (const int32_t *)p2;
82
83 if (*i1 > *i2)
84 return 1;
85 else if (*i1 < *i2)
86 return -1;
87 else
88 return 0;
89 }
90
91 /*
92 * stress_heapsort_cmp_2()
93 * heapsort comparison - reverse sort on int32 values
94 */
stress_heapsort_cmp_2(const void * p1,const void * p2)95 static int stress_heapsort_cmp_2(const void *p1, const void *p2)
96 {
97 return stress_heapsort_cmp_1(p2, p1);
98 }
99
100 /*
101 * stress_heapsort_cmp_3()
102 * heapsort comparison - sort on int8 values
103 */
stress_heapsort_cmp_3(const void * p1,const void * p2)104 static int stress_heapsort_cmp_3(const void *p1, const void *p2)
105 {
106 const int8_t *i1 = (const int8_t *)p1;
107 const int8_t *i2 = (const int8_t *)p2;
108
109 /* Force re-ordering on 8 bit value */
110 return *i1 - *i2;
111 }
112
113 /*
114 * stress_heapsort()
115 * stress heapsort
116 */
stress_heapsort(const stress_args_t * args)117 static int stress_heapsort(const stress_args_t *args)
118 {
119 uint64_t heapsort_size = DEFAULT_HEAPSORT_SIZE;
120 int32_t *data, *ptr;
121 size_t n, i;
122 struct sigaction old_action;
123 int ret;
124
125 if (!stress_get_setting("heapsort-size", &heapsort_size)) {
126 if (g_opt_flags & OPT_FLAGS_MAXIMIZE)
127 heapsort_size = MAX_HEAPSORT_SIZE;
128 if (g_opt_flags & OPT_FLAGS_MINIMIZE)
129 heapsort_size = MIN_HEAPSORT_SIZE;
130 }
131 n = (size_t)heapsort_size;
132
133 if ((data = calloc(n, sizeof(*data))) == NULL) {
134 pr_fail("%s: malloc failed, out of memory\n", args->name);
135 return EXIT_NO_RESOURCE;
136 }
137
138 if (stress_sighandler(args->name, SIGALRM, stress_heapsort_handler, &old_action) < 0) {
139 free(data);
140 return EXIT_FAILURE;
141 }
142
143 ret = sigsetjmp(jmp_env, 1);
144 if (ret) {
145 /*
146 * We return here if SIGALRM jmp'd back
147 */
148 (void)stress_sigrestore(args->name, SIGALRM, &old_action);
149 goto tidy;
150 }
151
152 /* This is expensive, do it once */
153 for (ptr = data, i = 0; i < n; i++)
154 *ptr++ = (int32_t)stress_mwc32();
155
156 stress_set_proc_state(args->name, STRESS_STATE_RUN);
157
158 do {
159 /* Sort "random" data */
160 if (heapsort(data, n, sizeof(*data), stress_heapsort_cmp_1) < 0) {
161 pr_fail("%s: heapsort of random data failed: %d (%s)\n",
162 args->name, errno, strerror(errno));
163 } else {
164 if (g_opt_flags & OPT_FLAGS_VERIFY) {
165 for (ptr = data, i = 0; i < n - 1; i++, ptr++) {
166 if (*ptr > *(ptr+1)) {
167 pr_fail("%s: sort error "
168 "detected, incorrect ordering "
169 "found\n", args->name);
170 break;
171 }
172 }
173 }
174 }
175 if (!keep_stressing_flag())
176 break;
177
178 /* Reverse sort */
179 if (heapsort(data, n, sizeof(*data), stress_heapsort_cmp_2) < 0) {
180 pr_fail("%s: reversed heapsort of random data failed: %d (%s)\n",
181 args->name, errno, strerror(errno));
182 } else {
183 if (g_opt_flags & OPT_FLAGS_VERIFY) {
184 for (ptr = data, i = 0; i < n - 1; i++, ptr++) {
185 if (*ptr < *(ptr+1)) {
186 pr_fail("%s: reverse sort "
187 "error detected, incorrect "
188 "ordering found\n", args->name);
189 break;
190 }
191 }
192 }
193 }
194 if (!keep_stressing_flag())
195 break;
196 /* And re-order by byte compare */
197 if (heapsort(data, n * 4, sizeof(uint8_t), stress_heapsort_cmp_3) < 0) {
198 pr_fail("%s: heapsort failed: %d (%s)\n",
199 args->name, errno, strerror(errno));
200 }
201
202 /* Reverse sort this again */
203 if (heapsort(data, n, sizeof(*data), stress_heapsort_cmp_2) < 0) {
204 pr_fail("%s: reversed heapsort of random data failed: %d (%s)\n",
205 args->name, errno, strerror(errno));
206 } else {
207 if (g_opt_flags & OPT_FLAGS_VERIFY) {
208 for (ptr = data, i = 0; i < n - 1; i++, ptr++) {
209 if (*ptr < *(ptr+1)) {
210 pr_fail("%s: reverse sort "
211 "error detected, incorrect "
212 "ordering found\n", args->name);
213 break;
214 }
215 }
216 }
217 }
218 if (!keep_stressing_flag())
219 break;
220
221 inc_counter(args);
222 } while (keep_stressing(args));
223
224 do_jmp = false;
225 (void)stress_sigrestore(args->name, SIGALRM, &old_action);
226 tidy:
227 stress_set_proc_state(args->name, STRESS_STATE_DEINIT);
228
229 free(data);
230
231 return EXIT_SUCCESS;
232 }
233
234 stressor_info_t stress_heapsort_info = {
235 .stressor = stress_heapsort,
236 .class = CLASS_CPU_CACHE | CLASS_CPU | CLASS_MEMORY,
237 .opt_set_funcs = opt_set_funcs,
238 .help = help
239 };
240 #else
241 stressor_info_t stress_heapsort_info = {
242 .stressor = stress_not_implemented,
243 .class = CLASS_CPU_CACHE | CLASS_CPU | CLASS_MEMORY,
244 .opt_set_funcs = opt_set_funcs,
245 .help = help
246 };
247 #endif
248