git.ozlabs.org Git - ccan/blob - 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 }