1 /*
2 * Copyright (c) 2005 Hewlett-Packard Development Company, L.P.
3 * Original Author: Hans Boehm
4 *
5 * This file may be redistributed and/or modified under the
6 * terms of the GNU General Public License as published by the Free Software
7 * Foundation; either version 2, or (at your option) any later version.
8 *
9 * It is distributed in the hope that it will be useful, but WITHOUT ANY
10 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11 * FOR A PARTICULAR PURPOSE. See the GNU General Public License in the
12 * file doc/COPYING for more details.
13 */
14
15 #if defined(HAVE_CONFIG_H)
16 # include "config.h"
17 #endif
18
19 #include "run_parallel.inc"
20
21 #include <stdlib.h>
22 #include <stdio.h>
23 #include "atomic_ops_malloc.h"
24
25 #ifndef MAX_NTHREADS
26 # define MAX_NTHREADS 100
27 #endif
28 #ifndef N_REVERSALS
29 # define N_REVERSALS 1000 /* must be even */
30 #endif
31 #ifndef LIST_LENGTH
32 # define LIST_LENGTH 1000
33 #endif
34 #ifndef LARGE_OBJ_SIZE
35 # define LARGE_OBJ_SIZE 200000
36 #endif
37
38 #ifdef USE_STANDARD_MALLOC
39 # define AO_malloc(n) malloc(n)
40 # define AO_free(p) free(p)
41 # define AO_malloc_enable_mmap()
42 #endif
43
44 typedef struct list_node {
45 struct list_node *next;
46 int data;
47 } ln;
48
cons(int d,ln * tail)49 ln *cons(int d, ln *tail)
50 {
51 static size_t extra = 0;
52 size_t my_extra = extra;
53 ln *result;
54 int * extras;
55 int i;
56
57 if (my_extra > 100)
58 extra = my_extra = 0;
59 else
60 ++extra;
61 result = AO_malloc(sizeof(ln) + sizeof(int)*my_extra);
62 if (result == 0)
63 {
64 fprintf(stderr, "Out of memory\n");
65 /* Normal for more than about 10 threads without mmap? */
66 abort();
67 }
68
69 result -> data = d;
70 result -> next = tail;
71 extras = (int *)(result+1);
72 for (i = 0; i < my_extra; ++i) extras[i] = 42;
73 return result;
74 }
75
print_list(ln * l)76 void print_list(ln *l)
77 {
78 ln *p;
79
80 for (p = l; p != 0; p = p -> next)
81 {
82 fprintf(stderr, "%d, ", p -> data);
83 }
84 fprintf(stderr, "\n");
85 }
86
87 /* Check that l contains numbers from m to n inclusive in ascending order */
check_list(ln * l,int m,int n)88 void check_list(ln *l, int m, int n)
89 {
90 ln *p;
91 int i;
92
93 for (p = l, i = m; p != 0; p = p -> next, ++i)
94 {
95 if (i != p -> data)
96 {
97 fprintf(stderr, "Found %d, expected %d\n", p -> data, i);
98 abort();
99 }
100 }
101 }
102
103 /* Create a list of integers from m to n */
104 ln *
make_list(int m,int n)105 make_list(int m, int n)
106 {
107 if (m > n) return 0;
108 return cons(m, make_list(m+1, n));
109 }
110
111 /* Reverse list x, and concatenate it to y, deallocating no longer needed */
112 /* nodes in x. */
113 ln *
reverse(ln * x,ln * y)114 reverse(ln *x, ln *y)
115 {
116 ln * result;
117
118 if (x == 0) return y;
119 result = reverse(x -> next, cons(x -> data, y));
120 AO_free(x);
121 return result;
122 }
123
dummy_test(void)124 int dummy_test(void) { return 1; }
125
run_one_test(void * arg)126 void * run_one_test(void * arg) {
127 ln * x = make_list(1, LIST_LENGTH);
128 int i;
129 char *p = AO_malloc(LARGE_OBJ_SIZE);
130 char *q;
131
132 if (0 == p) {
133 fprintf(stderr, "AO_malloc(%d) failed: This is normal without mmap\n",
134 LARGE_OBJ_SIZE);
135 AO_free(p);
136 } else {
137 p[0] = p[LARGE_OBJ_SIZE/2] = p[LARGE_OBJ_SIZE-1] = 'a';
138 q = AO_malloc(LARGE_OBJ_SIZE);
139 q[0] = q[LARGE_OBJ_SIZE/2] = q[LARGE_OBJ_SIZE-1] = 'b';
140 if (p[0] != 'a' || p[LARGE_OBJ_SIZE/2] != 'a'
141 || p[LARGE_OBJ_SIZE-1] != 'a') {
142 fprintf(stderr, "First large allocation smashed\n");
143 abort();
144 }
145 AO_free(p);
146 if (q[0] != 'b' || q[LARGE_OBJ_SIZE/2] != 'b'
147 || q[LARGE_OBJ_SIZE-1] != 'b') {
148 fprintf(stderr, "Second large allocation smashed\n");
149 abort();
150 }
151 AO_free(q);
152 }
153 # ifdef DEBUG_RUN_ONE_TEST
154 x = reverse(x, 0);
155 print_list(x);
156 x = reverse(x, 0);
157 print_list(x);
158 # endif
159 for (i = 0; i < N_REVERSALS; ++i) {
160 x = reverse(x, 0);
161 }
162 check_list(x, 1, LIST_LENGTH);
163 return 0;
164 }
165
main(int argc,char ** argv)166 int main(int argc, char **argv) {
167 int nthreads;
168 int exper_n;
169
170 if (1 == argc) {
171 # if !defined(HAVE_MMAP)
172 nthreads = 3;
173 # else
174 nthreads = 10;
175 # endif
176 } else if (2 == argc) {
177 nthreads = atoi(argv[1]);
178 if (nthreads < 1 || nthreads > MAX_NTHREADS) {
179 fprintf(stderr, "Invalid # of threads argument\n");
180 exit(1);
181 }
182 } else {
183 fprintf(stderr, "Usage: %s [# of threads]\n", argv[0]);
184 exit(1);
185 }
186 printf("Performing %d reversals of %d element lists in %d threads\n",
187 N_REVERSALS, LIST_LENGTH, nthreads);
188 AO_malloc_enable_mmap();
189 run_parallel(nthreads, run_one_test, dummy_test, "AO_malloc/AO_free");
190 return 0;
191 }
192