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