GNU Linux-libre 4.9.337-gnu1
[releases.git] / scripts / gcc-plugins / latent_entropy_plugin.c
1 /*
2  * Copyright 2012-2016 by the PaX Team <pageexec@freemail.hu>
3  * Copyright 2016 by Emese Revfy <re.emese@gmail.com>
4  * Licensed under the GPL v2
5  *
6  * Note: the choice of the license means that the compilation process is
7  *       NOT 'eligible' as defined by gcc's library exception to the GPL v3,
8  *       but for the kernel it doesn't matter since it doesn't link against
9  *       any of the gcc libraries
10  *
11  * This gcc plugin helps generate a little bit of entropy from program state,
12  * used throughout the uptime of the kernel. Here is an instrumentation example:
13  *
14  * before:
15  * void __latent_entropy test(int argc, char *argv[])
16  * {
17  *      if (argc <= 1)
18  *              printf("%s: no command arguments :(\n", *argv);
19  *      else
20  *              printf("%s: %d command arguments!\n", *argv, args - 1);
21  * }
22  *
23  * after:
24  * void __latent_entropy test(int argc, char *argv[])
25  * {
26  *      // latent_entropy_execute() 1.
27  *      unsigned long local_entropy;
28  *      // init_local_entropy() 1.
29  *      void *local_entropy_frameaddr;
30  *      // init_local_entropy() 3.
31  *      unsigned long tmp_latent_entropy;
32  *
33  *      // init_local_entropy() 2.
34  *      local_entropy_frameaddr = __builtin_frame_address(0);
35  *      local_entropy = (unsigned long) local_entropy_frameaddr;
36  *
37  *      // init_local_entropy() 4.
38  *      tmp_latent_entropy = latent_entropy;
39  *      // init_local_entropy() 5.
40  *      local_entropy ^= tmp_latent_entropy;
41  *
42  *      // latent_entropy_execute() 3.
43  *      if (argc <= 1) {
44  *              // perturb_local_entropy()
45  *              local_entropy += 4623067384293424948;
46  *              printf("%s: no command arguments :(\n", *argv);
47  *              // perturb_local_entropy()
48  *      } else {
49  *              local_entropy ^= 3896280633962944730;
50  *              printf("%s: %d command arguments!\n", *argv, args - 1);
51  *      }
52  *
53  *      // latent_entropy_execute() 4.
54  *      tmp_latent_entropy = rol(tmp_latent_entropy, local_entropy);
55  *      latent_entropy = tmp_latent_entropy;
56  * }
57  *
58  * TODO:
59  * - add ipa pass to identify not explicitly marked candidate functions
60  * - mix in more program state (function arguments/return values,
61  *   loop variables, etc)
62  * - more instrumentation control via attribute parameters
63  *
64  * BUGS:
65  * - none known
66  *
67  * Options:
68  * -fplugin-arg-latent_entropy_plugin-disable
69  *
70  * Attribute: __attribute__((latent_entropy))
71  *  The latent_entropy gcc attribute can be only on functions and variables.
72  *  If it is on a function then the plugin will instrument it. If the attribute
73  *  is on a variable then the plugin will initialize it with a random value.
74  *  The variable must be an integer, an integer array type or a structure
75  *  with integer fields.
76  */
77
78 #include "gcc-common.h"
79
80 __visible int plugin_is_GPL_compatible;
81
82 static GTY(()) tree latent_entropy_decl;
83
84 static struct plugin_info latent_entropy_plugin_info = {
85         .version        = "201606141920vanilla",
86         .help           = "disable\tturn off latent entropy instrumentation\n",
87 };
88
89 static unsigned HOST_WIDE_INT deterministic_seed;
90 static unsigned HOST_WIDE_INT rnd_buf[32];
91 static size_t rnd_idx = ARRAY_SIZE(rnd_buf);
92 static int urandom_fd = -1;
93
94 static unsigned HOST_WIDE_INT get_random_const(void)
95 {
96         if (deterministic_seed) {
97                 unsigned HOST_WIDE_INT w = deterministic_seed;
98                 w ^= w << 13;
99                 w ^= w >> 7;
100                 w ^= w << 17;
101                 deterministic_seed = w;
102                 return deterministic_seed;
103         }
104
105         if (urandom_fd < 0) {
106                 urandom_fd = open("/dev/urandom", O_RDONLY);
107                 gcc_assert(urandom_fd >= 0);
108         }
109         if (rnd_idx >= ARRAY_SIZE(rnd_buf)) {
110                 gcc_assert(read(urandom_fd, rnd_buf, sizeof(rnd_buf)) == sizeof(rnd_buf));
111                 rnd_idx = 0;
112         }
113         return rnd_buf[rnd_idx++];
114 }
115
116 static tree tree_get_random_const(tree type)
117 {
118         unsigned long long mask;
119
120         mask = 1ULL << (TREE_INT_CST_LOW(TYPE_SIZE(type)) - 1);
121         mask = 2 * (mask - 1) + 1;
122
123         if (TYPE_UNSIGNED(type))
124                 return build_int_cstu(type, mask & get_random_const());
125         return build_int_cst(type, mask & get_random_const());
126 }
127
128 static tree handle_latent_entropy_attribute(tree *node, tree name,
129                                                 tree args __unused,
130                                                 int flags __unused,
131                                                 bool *no_add_attrs)
132 {
133         tree type;
134 #if BUILDING_GCC_VERSION <= 4007
135         VEC(constructor_elt, gc) *vals;
136 #else
137         vec<constructor_elt, va_gc> *vals;
138 #endif
139
140         switch (TREE_CODE(*node)) {
141         default:
142                 *no_add_attrs = true;
143                 error("%qE attribute only applies to functions and variables",
144                         name);
145                 break;
146
147         case VAR_DECL:
148                 if (DECL_INITIAL(*node)) {
149                         *no_add_attrs = true;
150                         error("variable %qD with %qE attribute must not be initialized",
151                                 *node, name);
152                         break;
153                 }
154
155                 if (!TREE_STATIC(*node)) {
156                         *no_add_attrs = true;
157                         error("variable %qD with %qE attribute must not be local",
158                                 *node, name);
159                         break;
160                 }
161
162                 type = TREE_TYPE(*node);
163                 switch (TREE_CODE(type)) {
164                 default:
165                         *no_add_attrs = true;
166                         error("variable %qD with %qE attribute must be an integer or a fixed length integer array type or a fixed sized structure with integer fields",
167                                 *node, name);
168                         break;
169
170                 case RECORD_TYPE: {
171                         tree fld, lst = TYPE_FIELDS(type);
172                         unsigned int nelt = 0;
173
174                         for (fld = lst; fld; nelt++, fld = TREE_CHAIN(fld)) {
175                                 tree fieldtype;
176
177                                 fieldtype = TREE_TYPE(fld);
178                                 if (TREE_CODE(fieldtype) == INTEGER_TYPE)
179                                         continue;
180
181                                 *no_add_attrs = true;
182                                 error("structure variable %qD with %qE attribute has a non-integer field %qE",
183                                         *node, name, fld);
184                                 break;
185                         }
186
187                         if (fld)
188                                 break;
189
190 #if BUILDING_GCC_VERSION <= 4007
191                         vals = VEC_alloc(constructor_elt, gc, nelt);
192 #else
193                         vec_alloc(vals, nelt);
194 #endif
195
196                         for (fld = lst; fld; fld = TREE_CHAIN(fld)) {
197                                 tree random_const, fld_t = TREE_TYPE(fld);
198
199                                 random_const = tree_get_random_const(fld_t);
200                                 CONSTRUCTOR_APPEND_ELT(vals, fld, random_const);
201                         }
202
203                         /* Initialize the fields with random constants */
204                         DECL_INITIAL(*node) = build_constructor(type, vals);
205                         break;
206                 }
207
208                 /* Initialize the variable with a random constant */
209                 case INTEGER_TYPE:
210                         DECL_INITIAL(*node) = tree_get_random_const(type);
211                         break;
212
213                 case ARRAY_TYPE: {
214                         tree elt_type, array_size, elt_size;
215                         unsigned int i, nelt;
216                         HOST_WIDE_INT array_size_int, elt_size_int;
217
218                         elt_type = TREE_TYPE(type);
219                         elt_size = TYPE_SIZE_UNIT(TREE_TYPE(type));
220                         array_size = TYPE_SIZE_UNIT(type);
221
222                         if (TREE_CODE(elt_type) != INTEGER_TYPE || !array_size
223                                 || TREE_CODE(array_size) != INTEGER_CST) {
224                                 *no_add_attrs = true;
225                                 error("array variable %qD with %qE attribute must be a fixed length integer array type",
226                                         *node, name);
227                                 break;
228                         }
229
230                         array_size_int = TREE_INT_CST_LOW(array_size);
231                         elt_size_int = TREE_INT_CST_LOW(elt_size);
232                         nelt = array_size_int / elt_size_int;
233
234 #if BUILDING_GCC_VERSION <= 4007
235                         vals = VEC_alloc(constructor_elt, gc, nelt);
236 #else
237                         vec_alloc(vals, nelt);
238 #endif
239
240                         for (i = 0; i < nelt; i++) {
241                                 tree cst = size_int(i);
242                                 tree rand_cst = tree_get_random_const(elt_type);
243
244                                 CONSTRUCTOR_APPEND_ELT(vals, cst, rand_cst);
245                         }
246
247                         /*
248                          * Initialize the elements of the array with random
249                          * constants
250                          */
251                         DECL_INITIAL(*node) = build_constructor(type, vals);
252                         break;
253                 }
254                 }
255                 break;
256
257         case FUNCTION_DECL:
258                 break;
259         }
260
261         return NULL_TREE;
262 }
263
264 static struct attribute_spec latent_entropy_attr = {
265         .name                           = "latent_entropy",
266         .min_length                     = 0,
267         .max_length                     = 0,
268         .decl_required                  = true,
269         .type_required                  = false,
270         .function_type_required         = false,
271         .handler                        = handle_latent_entropy_attribute,
272 #if BUILDING_GCC_VERSION >= 4007
273         .affects_type_identity          = false
274 #endif
275 };
276
277 static void register_attributes(void *event_data __unused, void *data __unused)
278 {
279         register_attribute(&latent_entropy_attr);
280 }
281
282 static bool latent_entropy_gate(void)
283 {
284         tree list;
285
286         /* don't bother with noreturn functions for now */
287         if (TREE_THIS_VOLATILE(current_function_decl))
288                 return false;
289
290         /* gcc-4.5 doesn't discover some trivial noreturn functions */
291         if (EDGE_COUNT(EXIT_BLOCK_PTR_FOR_FN(cfun)->preds) == 0)
292                 return false;
293
294         list = DECL_ATTRIBUTES(current_function_decl);
295         return lookup_attribute("latent_entropy", list) != NULL_TREE;
296 }
297
298 static tree create_var(tree type, const char *name)
299 {
300         tree var;
301
302         var = create_tmp_var(type, name);
303         add_referenced_var(var);
304         mark_sym_for_renaming(var);
305         return var;
306 }
307
308 /*
309  * Set up the next operation and its constant operand to use in the latent
310  * entropy PRNG. When RHS is specified, the request is for perturbing the
311  * local latent entropy variable, otherwise it is for perturbing the global
312  * latent entropy variable where the two operands are already given by the
313  * local and global latent entropy variables themselves.
314  *
315  * The operation is one of add/xor/rol when instrumenting the local entropy
316  * variable and one of add/xor when perturbing the global entropy variable.
317  * Rotation is not used for the latter case because it would transmit less
318  * entropy to the global variable than the other two operations.
319  */
320 static enum tree_code get_op(tree *rhs)
321 {
322         static enum tree_code op;
323         unsigned HOST_WIDE_INT random_const;
324
325         random_const = get_random_const();
326
327         switch (op) {
328         case BIT_XOR_EXPR:
329                 op = PLUS_EXPR;
330                 break;
331
332         case PLUS_EXPR:
333                 if (rhs) {
334                         op = LROTATE_EXPR;
335                         /*
336                          * This code limits the value of random_const to
337                          * the size of a long for the rotation
338                          */
339                         random_const %= TYPE_PRECISION(long_unsigned_type_node);
340                         break;
341                 }
342
343         case LROTATE_EXPR:
344         default:
345                 op = BIT_XOR_EXPR;
346                 break;
347         }
348         if (rhs)
349                 *rhs = build_int_cstu(long_unsigned_type_node, random_const);
350         return op;
351 }
352
353 static gimple create_assign(enum tree_code code, tree lhs, tree op1,
354                                 tree op2)
355 {
356         return gimple_build_assign_with_ops(code, lhs, op1, op2);
357 }
358
359 static void perturb_local_entropy(basic_block bb, tree local_entropy)
360 {
361         gimple_stmt_iterator gsi;
362         gimple assign;
363         tree rhs;
364         enum tree_code op;
365
366         op = get_op(&rhs);
367         assign = create_assign(op, local_entropy, local_entropy, rhs);
368         gsi = gsi_after_labels(bb);
369         gsi_insert_before(&gsi, assign, GSI_NEW_STMT);
370         update_stmt(assign);
371 }
372
373 static void __perturb_latent_entropy(gimple_stmt_iterator *gsi,
374                                         tree local_entropy)
375 {
376         gimple assign;
377         tree temp;
378         enum tree_code op;
379
380         /* 1. create temporary copy of latent_entropy */
381         temp = create_var(long_unsigned_type_node, "temp_latent_entropy");
382
383         /* 2. read... */
384         add_referenced_var(latent_entropy_decl);
385         mark_sym_for_renaming(latent_entropy_decl);
386         assign = gimple_build_assign(temp, latent_entropy_decl);
387         gsi_insert_before(gsi, assign, GSI_NEW_STMT);
388         update_stmt(assign);
389
390         /* 3. ...modify... */
391         op = get_op(NULL);
392         assign = create_assign(op, temp, temp, local_entropy);
393         gsi_insert_after(gsi, assign, GSI_NEW_STMT);
394         update_stmt(assign);
395
396         /* 4. ...write latent_entropy */
397         assign = gimple_build_assign(latent_entropy_decl, temp);
398         gsi_insert_after(gsi, assign, GSI_NEW_STMT);
399         update_stmt(assign);
400 }
401
402 static bool handle_tail_calls(basic_block bb, tree local_entropy)
403 {
404         gimple_stmt_iterator gsi;
405
406         for (gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) {
407                 gcall *call;
408                 gimple stmt = gsi_stmt(gsi);
409
410                 if (!is_gimple_call(stmt))
411                         continue;
412
413                 call = as_a_gcall(stmt);
414                 if (!gimple_call_tail_p(call))
415                         continue;
416
417                 __perturb_latent_entropy(&gsi, local_entropy);
418                 return true;
419         }
420
421         return false;
422 }
423
424 static void perturb_latent_entropy(tree local_entropy)
425 {
426         edge_iterator ei;
427         edge e, last_bb_e;
428         basic_block last_bb;
429
430         gcc_assert(single_pred_p(EXIT_BLOCK_PTR_FOR_FN(cfun)));
431         last_bb_e = single_pred_edge(EXIT_BLOCK_PTR_FOR_FN(cfun));
432
433         FOR_EACH_EDGE(e, ei, last_bb_e->src->preds) {
434                 if (ENTRY_BLOCK_PTR_FOR_FN(cfun) == e->src)
435                         continue;
436                 if (EXIT_BLOCK_PTR_FOR_FN(cfun) == e->src)
437                         continue;
438
439                 handle_tail_calls(e->src, local_entropy);
440         }
441
442         last_bb = single_pred(EXIT_BLOCK_PTR_FOR_FN(cfun));
443         if (!handle_tail_calls(last_bb, local_entropy)) {
444                 gimple_stmt_iterator gsi = gsi_last_bb(last_bb);
445
446                 __perturb_latent_entropy(&gsi, local_entropy);
447         }
448 }
449
450 static void init_local_entropy(basic_block bb, tree local_entropy)
451 {
452         gimple assign, call;
453         tree frame_addr, rand_const, tmp, fndecl, udi_frame_addr;
454         enum tree_code op;
455         unsigned HOST_WIDE_INT rand_cst;
456         gimple_stmt_iterator gsi = gsi_after_labels(bb);
457
458         /* 1. create local_entropy_frameaddr */
459         frame_addr = create_var(ptr_type_node, "local_entropy_frameaddr");
460
461         /* 2. local_entropy_frameaddr = __builtin_frame_address() */
462         fndecl = builtin_decl_implicit(BUILT_IN_FRAME_ADDRESS);
463         call = gimple_build_call(fndecl, 1, integer_zero_node);
464         gimple_call_set_lhs(call, frame_addr);
465         gsi_insert_before(&gsi, call, GSI_NEW_STMT);
466         update_stmt(call);
467
468         udi_frame_addr = fold_convert(long_unsigned_type_node, frame_addr);
469         assign = gimple_build_assign(local_entropy, udi_frame_addr);
470         gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
471         update_stmt(assign);
472
473         /* 3. create temporary copy of latent_entropy */
474         tmp = create_var(long_unsigned_type_node, "temp_latent_entropy");
475
476         /* 4. read the global entropy variable into local entropy */
477         add_referenced_var(latent_entropy_decl);
478         mark_sym_for_renaming(latent_entropy_decl);
479         assign = gimple_build_assign(tmp, latent_entropy_decl);
480         gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
481         update_stmt(assign);
482
483         /* 5. mix local_entropy_frameaddr into local entropy */
484         assign = create_assign(BIT_XOR_EXPR, local_entropy, local_entropy, tmp);
485         gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
486         update_stmt(assign);
487
488         rand_cst = get_random_const();
489         rand_const = build_int_cstu(long_unsigned_type_node, rand_cst);
490         op = get_op(NULL);
491         assign = create_assign(op, local_entropy, local_entropy, rand_const);
492         gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
493         update_stmt(assign);
494 }
495
496 static bool create_latent_entropy_decl(void)
497 {
498         varpool_node_ptr node;
499
500         if (latent_entropy_decl != NULL_TREE)
501                 return true;
502
503         FOR_EACH_VARIABLE(node) {
504                 tree name, var = NODE_DECL(node);
505
506                 if (DECL_NAME_LENGTH(var) < sizeof("latent_entropy") - 1)
507                         continue;
508
509                 name = DECL_NAME(var);
510                 if (strcmp(IDENTIFIER_POINTER(name), "latent_entropy"))
511                         continue;
512
513                 latent_entropy_decl = var;
514                 break;
515         }
516
517         return latent_entropy_decl != NULL_TREE;
518 }
519
520 static unsigned int latent_entropy_execute(void)
521 {
522         basic_block bb;
523         tree local_entropy;
524
525         if (!create_latent_entropy_decl())
526                 return 0;
527
528         /* prepare for step 2 below */
529         gcc_assert(single_succ_p(ENTRY_BLOCK_PTR_FOR_FN(cfun)));
530         bb = single_succ(ENTRY_BLOCK_PTR_FOR_FN(cfun));
531         if (!single_pred_p(bb)) {
532                 split_edge(single_succ_edge(ENTRY_BLOCK_PTR_FOR_FN(cfun)));
533                 gcc_assert(single_succ_p(ENTRY_BLOCK_PTR_FOR_FN(cfun)));
534                 bb = single_succ(ENTRY_BLOCK_PTR_FOR_FN(cfun));
535         }
536
537         /* 1. create the local entropy variable */
538         local_entropy = create_var(long_unsigned_type_node, "local_entropy");
539
540         /* 2. initialize the local entropy variable */
541         init_local_entropy(bb, local_entropy);
542
543         bb = bb->next_bb;
544
545         /*
546          * 3. instrument each BB with an operation on the
547          *    local entropy variable
548          */
549         while (bb != EXIT_BLOCK_PTR_FOR_FN(cfun)) {
550                 perturb_local_entropy(bb, local_entropy);
551                 bb = bb->next_bb;
552         };
553
554         /* 4. mix local entropy into the global entropy variable */
555         perturb_latent_entropy(local_entropy);
556         return 0;
557 }
558
559 static void latent_entropy_start_unit(void *gcc_data __unused,
560                                         void *user_data __unused)
561 {
562         tree type, id;
563         int quals;
564
565         if (in_lto_p)
566                 return;
567
568         /* extern volatile unsigned long latent_entropy */
569         quals = TYPE_QUALS(long_unsigned_type_node) | TYPE_QUAL_VOLATILE;
570         type = build_qualified_type(long_unsigned_type_node, quals);
571         id = get_identifier("latent_entropy");
572         latent_entropy_decl = build_decl(UNKNOWN_LOCATION, VAR_DECL, id, type);
573
574         TREE_STATIC(latent_entropy_decl) = 1;
575         TREE_PUBLIC(latent_entropy_decl) = 1;
576         TREE_USED(latent_entropy_decl) = 1;
577         DECL_PRESERVE_P(latent_entropy_decl) = 1;
578         TREE_THIS_VOLATILE(latent_entropy_decl) = 1;
579         DECL_EXTERNAL(latent_entropy_decl) = 1;
580         DECL_ARTIFICIAL(latent_entropy_decl) = 1;
581         lang_hooks.decls.pushdecl(latent_entropy_decl);
582 }
583
584 #define PASS_NAME latent_entropy
585 #define PROPERTIES_REQUIRED PROP_gimple_leh | PROP_cfg
586 #define TODO_FLAGS_FINISH TODO_verify_ssa | TODO_verify_stmts | TODO_dump_func \
587         | TODO_update_ssa
588 #include "gcc-generate-gimple-pass.h"
589
590 __visible int plugin_init(struct plugin_name_args *plugin_info,
591                           struct plugin_gcc_version *version)
592 {
593         bool enabled = true;
594         const char * const plugin_name = plugin_info->base_name;
595         const int argc = plugin_info->argc;
596         const struct plugin_argument * const argv = plugin_info->argv;
597         int i;
598
599         struct register_pass_info latent_entropy_pass_info;
600
601         /*
602          * Call get_random_seed() with noinit=true, so that this returns
603          * 0 in the case where no seed has been passed via -frandom-seed.
604          */
605         deterministic_seed = get_random_seed(true);
606
607         latent_entropy_pass_info.pass           = make_latent_entropy_pass();
608         latent_entropy_pass_info.reference_pass_name            = "optimized";
609         latent_entropy_pass_info.ref_pass_instance_number       = 1;
610         latent_entropy_pass_info.pos_op         = PASS_POS_INSERT_BEFORE;
611         static const struct ggc_root_tab gt_ggc_r_gt_latent_entropy[] = {
612                 {
613                         .base = &latent_entropy_decl,
614                         .nelt = 1,
615                         .stride = sizeof(latent_entropy_decl),
616                         .cb = &gt_ggc_mx_tree_node,
617                         .pchw = &gt_pch_nx_tree_node
618                 },
619                 LAST_GGC_ROOT_TAB
620         };
621
622         if (!plugin_default_version_check(version, &gcc_version)) {
623                 error(G_("incompatible gcc/plugin versions"));
624                 return 1;
625         }
626
627         for (i = 0; i < argc; ++i) {
628                 if (!(strcmp(argv[i].key, "disable"))) {
629                         enabled = false;
630                         continue;
631                 }
632                 error(G_("unkown option '-fplugin-arg-%s-%s'"), plugin_name, argv[i].key);
633         }
634
635         register_callback(plugin_name, PLUGIN_INFO, NULL,
636                                 &latent_entropy_plugin_info);
637         if (enabled) {
638                 register_callback(plugin_name, PLUGIN_START_UNIT,
639                                         &latent_entropy_start_unit, NULL);
640                 register_callback(plugin_name, PLUGIN_REGISTER_GGC_ROOTS,
641                                   NULL, (void *)&gt_ggc_r_gt_latent_entropy);
642                 register_callback(plugin_name, PLUGIN_PASS_MANAGER_SETUP, NULL,
643                                         &latent_entropy_pass_info);
644         }
645         register_callback(plugin_name, PLUGIN_ATTRIBUTES, register_attributes,
646                                 NULL);
647
648         return 0;
649 }