1 /*
2 * Copyright (C) 2013-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 typedef struct skip_node {
28 unsigned long value;
29 struct skip_node *skip_nodes[1];
30 } skip_node_t;
31
32 typedef struct {
33 size_t level;
34 size_t max_level;
35 skip_node_t *head;
36 } skip_list_t;
37
38 static const stress_help_t help[] = {
39 { NULL, "skiplist N", "start N workers that exercise a skiplist search" },
40 { NULL, "skiplist-ops N", "stop after N skiplist search bogo operations" },
41 { NULL, "skiplist-size N", "number of 32 bit integers to add to skiplist" },
42 { NULL, NULL, NULL }
43 };
44
45 /*
46 * stress_set_skiplist_size()
47 * set skiplist size from given option string
48 */
stress_set_skiplist_size(const char * opt)49 static int stress_set_skiplist_size(const char *opt)
50 {
51 uint64_t skiplist_size;
52
53 skiplist_size = stress_get_uint64(opt);
54 stress_check_range("skiplist-size", skiplist_size,
55 MIN_SKIPLIST_SIZE, MAX_SKIPLIST_SIZE);
56 return stress_set_setting("skiplist-size", TYPE_ID_UINT64, &skiplist_size);
57 }
58
59 /*
60 * skip_list_random_level()
61 * generate a quasi-random skip list level
62 */
skip_list_random_level(const size_t max_level)63 static inline size_t skip_list_random_level(const size_t max_level)
64 {
65 register size_t level = 1;
66 register size_t r = stress_mwc32();
67
68 while ((r & 1) && (level < max_level)) {
69 r >>= 1;
70 level++;
71 }
72 return level;
73 }
74
75
76 /*
77 * skip_node_alloc()
78 * allocate a skip list node
79 */
skip_node_alloc(const size_t levels)80 static skip_node_t *skip_node_alloc(const size_t levels)
81 {
82 const size_t sz = sizeof(skip_node_t) + (levels * sizeof(skip_node_t *));
83
84 return (skip_node_t *)calloc(1, sz);
85 }
86
87 /*
88 * skip_list_init
89 * initialize the skip list, return NULL if failed
90 */
skip_list_init(skip_list_t * list,const size_t max_level)91 static skip_list_t *skip_list_init(skip_list_t *list, const size_t max_level)
92 {
93 register size_t i;
94 skip_node_t *head;
95
96 head = skip_node_alloc(max_level);
97 if (!head)
98 return NULL;
99 list->level = 1;
100 list->max_level = max_level;
101 list->head = head;
102 head->value = INT_MAX;
103
104 for (i = 0; i <= max_level; i++)
105 head->skip_nodes[i] = list->head;
106
107 return list;
108 }
109
110 /*
111 * skip_list_insert()
112 * insert a value into the skiplist
113 */
skip_list_insert(skip_list_t * list,const unsigned long value)114 static skip_node_t *skip_list_insert(skip_list_t *list, const unsigned long value)
115 {
116 skip_node_t *skip_nodes[list->max_level + 1];
117 skip_node_t *skip_node = list->head;
118 register size_t i, level;
119
120 for (i = list->level; i >= 1; i--) {
121 while (skip_node->skip_nodes[i]->value < value)
122 skip_node = skip_node->skip_nodes[i];
123
124 skip_nodes[i] = skip_node;
125 }
126 skip_node = skip_node->skip_nodes[1];
127
128 if (value == skip_node->value) {
129 skip_node->value = value;
130 return skip_node;
131 }
132
133 level = skip_list_random_level(list->max_level);
134 if (level > list->level) {
135 for (i = list->level + 1; i <= level; i++)
136 skip_nodes[i] = list->head;
137
138 list->level = level;
139 }
140
141 skip_node = skip_node_alloc(level);
142 if (!skip_node)
143 return NULL;
144 skip_node->value = value;
145 for (i = 1; i <= level; i++) {
146 skip_node->skip_nodes[i] = skip_nodes[i]->skip_nodes[i];
147 skip_nodes[i]->skip_nodes[i] = skip_node;
148 }
149 return skip_node;
150 }
151
152 /*
153 * skip_list_search()
154 * search the skiplist for a specific value
155 */
skip_list_search(skip_list_t * list,const unsigned long value)156 static skip_node_t *skip_list_search(skip_list_t *list, const unsigned long value)
157 {
158 skip_node_t *skip_node = list->head;
159 register size_t i;
160
161 for (i = list->level; i >= 1; i--) {
162 while (skip_node->skip_nodes[i]->value < value)
163 skip_node = skip_node->skip_nodes[i];
164 }
165 return skip_node->skip_nodes[1]->value == value ? skip_node->skip_nodes[1] : NULL;
166 }
167
168 /*
169 * skip_list_ln2()
170 * compute maximum skiplist level
171 */
skip_list_ln2(unsigned long n)172 static inline unsigned long skip_list_ln2(unsigned long n)
173 {
174 register unsigned long i = 0;
175
176 while (n) {
177 i++;
178 n >>= 1;
179 }
180 return i;
181 }
182
183 /*
184 * skip_list_free()
185 * free a skip list
186 */
skip_list_free(skip_list_t * list)187 static void skip_list_free(skip_list_t *list)
188 {
189 skip_node_t *head = list->head;
190 skip_node_t *skip_node = head;
191
192 while (skip_node && skip_node->skip_nodes[1] != head) {
193 skip_node_t *next = skip_node->skip_nodes[1];
194
195 free(skip_node);
196 skip_node = next;
197 }
198 if (skip_node)
199 free(skip_node);
200 }
201
202 /*
203 * stress_skiplist()
204 * stress skiplist
205 */
stress_skiplist(const stress_args_t * args)206 static int stress_skiplist(const stress_args_t *args)
207 {
208 unsigned long n, i, ln2n;
209 uint64_t skiplist_size = 1024;
210
211 if (!stress_get_setting("skiplist-size", &skiplist_size)) {
212 if (g_opt_flags & OPT_FLAGS_MAXIMIZE)
213 skiplist_size = MAX_SKIPLIST_SIZE;
214 if (g_opt_flags & OPT_FLAGS_MINIMIZE)
215 skiplist_size = MIN_SKIPLIST_SIZE;
216 }
217 n = (unsigned long)skiplist_size;
218 ln2n = skip_list_ln2(n);
219
220 stress_set_proc_state(args->name, STRESS_STATE_RUN);
221
222 do {
223 skip_list_t list;
224
225 if (!skip_list_init(&list, ln2n)) {
226 pr_inf("%s: out of memory initializing the skip list\n",
227 args->name);
228 return EXIT_NO_RESOURCE;
229 }
230
231 for (i = 0; i < n; i++) {
232 unsigned long v = (i >> 1) ^ i;
233
234 if (!skip_list_insert(&list, v)) {
235 pr_inf("%s: out of memory initializing the skip list\n",
236 args->name);
237 skip_list_free(&list);
238 return EXIT_NO_RESOURCE;
239 }
240 }
241
242 for (i = 0; i < n; i++) {
243 unsigned long v = (i >> 1) ^ i;
244
245 if (!skip_list_search(&list, v))
246 pr_fail("%s node containing value %lu was not found\n",
247 args->name, v);
248 }
249 skip_list_free(&list);
250
251 inc_counter(args);
252 } while (keep_stressing(args));
253
254 stress_set_proc_state(args->name, STRESS_STATE_DEINIT);
255
256 return EXIT_SUCCESS;
257 }
258
259 static const stress_opt_set_func_t opt_set_funcs[] = {
260 { OPT_skiplist_size, stress_set_skiplist_size },
261 { 0, NULL },
262 };
263
264 stressor_info_t stress_skiplist_info = {
265 .stressor = stress_skiplist,
266 .class = CLASS_CPU_CACHE | CLASS_CPU | CLASS_MEMORY,
267 .opt_set_funcs = opt_set_funcs,
268 .help = help
269 };
270