e25c7e9b69163996c96ad22081307ad24b729355
[ccan] / ccan / tal / benchmark / samba-allocs.c
1 /* Grab dump of Samba4 talloc tree to do benchmarks on it. */
2 #include <ccan/talloc/talloc.h>
3 #include <ccan/tal/tal.h>
4 #include <ccan/time/time.h>
5 #include <ccan/err/err.h>
6 #include <ccan/str/str.h>
7 #include <string.h>
8 #include <assert.h>
9 #include <sys/types.h>
10 #include <sys/stat.h>
11 #include <unistd.h>
12 #include <fcntl.h>
13
14 struct node {
15         void *n;
16         struct node *parent;
17         char *name;
18         bool destructor;
19         size_t len;
20         unsigned int num_children;
21         struct node *children[0];
22 };
23
24 static int node_count;
25
26 static struct node *new_node(void)
27 {
28         node_count++;
29         return calloc(sizeof(struct node), 1);
30 }
31
32 /* struct db_context              contains    282 bytes in   5 blocks (ref 0) d=(nil) 0x1f64e70 */
33 static struct node *parse(const char *line)
34 {
35         struct node *n = new_node();
36         const char *p;
37
38         p = strstr(line, " contains ");
39         p += strlen(" contains ");
40         p += strspn(line, " ");
41         n->len = strtol(p, NULL, 0);
42         p = strstr(p, "d=");
43         if (p[2] != '(')
44                 n->destructor = true;
45         return n;
46 }
47
48 static void add_child(struct node *parent, struct node *child)
49 {
50         unsigned int i;
51         struct node *oldp = parent;
52
53         parent = realloc(parent, sizeof(*parent)
54                          + sizeof(parent->children[0]) * (parent->num_children+1));
55         parent->children[parent->num_children++] = child;
56         child->parent = parent;
57
58         if (parent == oldp)
59                 return;
60
61         /* Fix up children's parent pointers. */
62         for (i = 0; i < parent->num_children-1; i++) {
63                 assert(parent->children[i]->parent == oldp);
64                 parent->children[i]->parent = parent;
65         }
66
67         /* Fix up parent's child pointer. */
68         if (parent->parent) {
69                 assert(parent->parent->children[parent->parent->num_children-1]
70                        == oldp);
71                 parent->parent->children[parent->parent->num_children-1]
72                         = parent;
73         }
74 }
75
76 /* Random string of required length */
77 static char *namelen(int len)
78 {
79         char *p = malloc(len);
80         memset(p, 'x', len-1);
81         p[len-1] = '\0';
82         return p;
83 }
84
85 static struct node *read_nodes(FILE *f)
86 {
87         char line[4096];
88         unsigned int curr_indent = 0, indent;
89         struct node *n, *curr = new_node();
90
91         /* Ignore first line */
92         fgets(line, 4096, f);
93
94         while (fgets(line, 4096, f)) {
95                 bool is_name;
96
97                 indent = strspn(line, " ");
98
99                 /* Ignore references for now. */
100                 if (strstarts(line + indent, "reference to: "))
101                         continue;
102
103                 /* Blank name?  Use offset of 'contains' to guess indent! */
104                 if (strstarts(line + indent, "contains "))
105                         indent -= 31;
106
107                 is_name = strstarts(line + indent, ".name ");
108
109                 n = parse(line + indent);
110                 if (is_name) {
111                         curr->name = namelen(n->len);
112                         free(n);
113                 } else {
114                         if (indent > curr_indent) {
115                                 assert(indent == curr_indent + 4);
116                                 curr_indent += 4;
117                         } else {
118                                 /* Go back up to parent. */
119                                 for (curr_indent += 4;
120                                      curr_indent != indent;
121                                      curr_indent -= 4)
122                                         curr = curr->parent;
123                         }
124                         add_child(curr, n);
125                         curr = n;
126                 }
127         }
128         while (curr->parent) {
129                 curr = curr->parent;
130                 curr_indent -= 4;
131         }
132         assert(curr_indent == 0);
133         return curr;
134 }
135
136 static int unused_talloc_destructor(void *p)
137 {
138         return 0;
139 }
140
141 static void do_tallocs(struct node *node)
142 {
143         unsigned int i;
144         static int count;
145
146         if (count++ % 16 == 0)
147                 node->n = talloc_array(node->parent ? node->parent->n : NULL,
148                                        char, node->len);
149         else
150                 node->n = talloc_size(node->parent ? node->parent->n : NULL,
151                                       node->len);
152         if (node->destructor)
153                 talloc_set_destructor(node->n, unused_talloc_destructor);
154         if (node->name)
155                 talloc_set_name(node->n, "%s", node->name);
156
157         for (i = 0; i < node->num_children; i++)
158                 do_tallocs(node->children[i]);
159 }
160
161 static void free_tallocs(struct node *node)
162 {
163         unsigned int i;
164
165         for (i = 0; i < node->num_children; i++)
166                 free_tallocs(node->children[i]);
167
168         talloc_free(node->n);
169 }
170
171 static void unused_tal_destructor(void *p)
172 {
173 }
174
175 static void do_tals(struct node *node)
176 {
177         unsigned int i;
178         static int count;
179
180         /* Tal pays a penalty for arrays, but we can't tell which is an array
181          * and which isn't.  Grepping samba source gives 1221 talloc_array of
182          * 33137 talloc occurrences, so conservatively assume 1 in 16 */
183         if (count++ % 16 == 0)
184                 node->n = tal_arr(node->parent ? node->parent->n : NULL,
185                                   char, node->len);
186         else
187                 node->n = tal_alloc_(node->parent ? node->parent->n : NULL,
188                                      node->len, false, TAL_LABEL(type, ""));
189
190         if (node->destructor)
191                 tal_add_destructor(node->n, unused_tal_destructor);
192         if (node->name)
193                 tal_set_name(node->n, node->name);
194
195         for (i = 0; i < node->num_children; i++)
196                 do_tals(node->children[i]);
197 }
198
199 static void free_tals(struct node *node)
200 {
201         unsigned int i;
202
203         for (i = 0; i < node->num_children; i++)
204                 free_tals(node->children[i]);
205
206         tal_free(node->n);
207 }
208
209 static void do_mallocs(struct node *node)
210 {
211         unsigned int i;
212
213         node->n = malloc(node->len + (node->name ? strlen(node->name) + 1 : 1));
214
215         for (i = 0; i < node->num_children; i++)
216                 do_mallocs(node->children[i]);
217 }
218
219 static void free_mallocs(struct node *node)
220 {
221         unsigned int i;
222
223         for (i = 0; i < node->num_children; i++)
224                 free_mallocs(node->children[i]);
225
226         free(node->n);
227 }
228
229 /* See proc(5): field 23 is vsize, 24 is rss (in pages) */
230 static void dump_vsize(void)
231 {
232         int fd, i;
233         char buf[1000], *p = buf;
234
235         sprintf(buf, "/proc/%u/stat", getpid());
236         fd = open(buf, O_RDONLY);
237         read(fd, buf, sizeof(buf));
238         close(fd);
239
240         for (i = 0; i < 22; i++) {
241                 p += strcspn(p, " ");
242                 p += strspn(p, " ");
243         }
244         i = atoi(p);
245         printf("Virtual size = %i, ", i);
246         p += strcspn(p, " ");
247         p += strspn(p, " ");
248         i = atoi(p);
249         printf("RSS = %i\n", i * getpagesize());
250 }
251
252 #define LOOPS 1000
253
254 int main(int argc, char *argv[])
255 {
256         struct timespec start, alloc_time, free_time;
257         struct node *root;
258         unsigned int i;
259         FILE *f;
260         bool run_talloc = true, run_tal = true, run_malloc = true;
261
262         f = argv[1] ? fopen(argv[1], "r") : stdin;
263         root = read_nodes(f);
264         fclose(f);
265         printf("Read %u nodes\n", node_count);
266
267         if (argc > 2) {
268                 if (streq(argv[2], "--talloc-size")) {
269                         do_tallocs(root);
270                         dump_vsize();
271                         exit(0);
272                 }
273                 if (streq(argv[2], "--tal-size")) {
274                         do_tals(root);
275                         dump_vsize();
276                         exit(0);
277                 }
278                 if (strcmp(argv[2], "--talloc") == 0)
279                         run_tal = run_malloc = false;
280                 else if (strcmp(argv[2], "--tal") == 0)
281                         run_talloc = run_malloc = false;
282                 else if (strcmp(argv[2], "--malloc") == 0)
283                         run_talloc = run_tal = false;
284                 else
285                         errx(1, "Bad flag %s", argv[2]);
286         }
287
288         if (!run_malloc)
289                 goto after_malloc;
290
291         alloc_time.tv_sec = alloc_time.tv_nsec = 0;
292         free_time.tv_sec = free_time.tv_nsec = 0;
293         for (i = 0; i < LOOPS; i++) {
294                 start = time_now();
295                 do_mallocs(root);
296                 alloc_time = time_add(alloc_time, time_sub(time_now(), start));
297
298                 start = time_now();
299                 free_mallocs(root);
300                 free_time = time_add(free_time, time_sub(time_now(), start));
301         }
302         alloc_time = time_divide(alloc_time, i);
303         free_time = time_divide(free_time, i);
304         printf("Malloc time:             %lluns\n", time_to_nsec(alloc_time));
305         printf("Free time:               %lluns\n", time_to_nsec(free_time));
306
307 after_malloc:
308         if (!run_talloc)
309                 goto after_talloc;
310
311         alloc_time.tv_sec = alloc_time.tv_nsec = 0;
312         free_time.tv_sec = free_time.tv_nsec = 0;
313         for (i = 0; i < LOOPS; i++) {
314                 start = time_now();
315                 do_tallocs(root);
316                 alloc_time = time_add(alloc_time, time_sub(time_now(), start));
317
318                 start = time_now();
319                 free_tallocs(root);
320                 free_time = time_add(free_time, time_sub(time_now(), start));
321         }
322         alloc_time = time_divide(alloc_time, i);
323         free_time = time_divide(free_time, i);
324         printf("Talloc time:             %lluns\n", time_to_nsec(alloc_time));
325         printf("talloc_free time:        %lluns\n", time_to_nsec(free_time));
326
327         free_time.tv_sec = free_time.tv_nsec = 0;
328         for (i = 0; i < LOOPS; i++) {
329                 do_tallocs(root);
330
331                 start = time_now();
332                 talloc_free(root->n);
333                 free_time = time_add(free_time, time_sub(time_now(), start));
334         }
335         free_time = time_divide(free_time, i);
336         printf("Single talloc_free time: %lluns\n", time_to_nsec(free_time));
337
338 after_talloc:
339         if (!run_tal)
340                 goto after_tal;
341
342         alloc_time.tv_sec = alloc_time.tv_nsec = 0;
343         free_time.tv_sec = free_time.tv_nsec = 0;
344         for (i = 0; i < LOOPS; i++) {
345                 start = time_now();
346                 do_tals(root);
347                 alloc_time = time_add(alloc_time, time_sub(time_now(), start));
348
349                 start = time_now();
350                 free_tals(root);
351                 free_time = time_add(free_time, time_sub(time_now(), start));
352         }
353         alloc_time = time_divide(alloc_time, i);
354         free_time = time_divide(free_time, i);
355         printf("Tal time:                %lluns\n", time_to_nsec(alloc_time));
356         printf("Tal_free time:           %lluns\n", time_to_nsec(free_time));
357
358         free_time.tv_sec = free_time.tv_nsec = 0;
359         for (i = 0; i < LOOPS; i++) {
360                 do_tals(root);
361
362                 start = time_now();
363                 tal_free(root->n);
364                 free_time = time_add(free_time, time_sub(time_now(), start));
365         }
366         free_time = time_divide(free_time, i);
367         printf("Single tal_free time:    %lluns\n", time_to_nsec(free_time));
368 after_tal:
369
370         return 0;
371 }