65264960910d36878c5b8be4213638e09d3af728
[muen/linux.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 seed;
90 /*
91  * get_random_seed() (this is a GCC function) generates the seed.
92  * This is a simple random generator without any cryptographic security because
93  * the entropy doesn't come from here.
94  */
95 static unsigned HOST_WIDE_INT get_random_const(void)
96 {
97         unsigned int i;
98         unsigned HOST_WIDE_INT ret = 0;
99
100         for (i = 0; i < 8 * sizeof(ret); i++) {
101                 ret = (ret << 1) | (seed & 1);
102                 seed >>= 1;
103                 if (ret & 1)
104                         seed ^= 0xD800000000000000ULL;
105         }
106
107         return ret;
108 }
109
110 static tree tree_get_random_const(tree type)
111 {
112         unsigned long long mask;
113
114         mask = 1ULL << (TREE_INT_CST_LOW(TYPE_SIZE(type)) - 1);
115         mask = 2 * (mask - 1) + 1;
116
117         if (TYPE_UNSIGNED(type))
118                 return build_int_cstu(type, mask & get_random_const());
119         return build_int_cst(type, mask & get_random_const());
120 }
121
122 static tree handle_latent_entropy_attribute(tree *node, tree name,
123                                                 tree args __unused,
124                                                 int flags __unused,
125                                                 bool *no_add_attrs)
126 {
127         tree type;
128 #if BUILDING_GCC_VERSION <= 4007
129         VEC(constructor_elt, gc) *vals;
130 #else
131         vec<constructor_elt, va_gc> *vals;
132 #endif
133
134         switch (TREE_CODE(*node)) {
135         default:
136                 *no_add_attrs = true;
137                 error("%qE attribute only applies to functions and variables",
138                         name);
139                 break;
140
141         case VAR_DECL:
142                 if (DECL_INITIAL(*node)) {
143                         *no_add_attrs = true;
144                         error("variable %qD with %qE attribute must not be initialized",
145                                 *node, name);
146                         break;
147                 }
148
149                 if (!TREE_STATIC(*node)) {
150                         *no_add_attrs = true;
151                         error("variable %qD with %qE attribute must not be local",
152                                 *node, name);
153                         break;
154                 }
155
156                 type = TREE_TYPE(*node);
157                 switch (TREE_CODE(type)) {
158                 default:
159                         *no_add_attrs = true;
160                         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",
161                                 *node, name);
162                         break;
163
164                 case RECORD_TYPE: {
165                         tree fld, lst = TYPE_FIELDS(type);
166                         unsigned int nelt = 0;
167
168                         for (fld = lst; fld; nelt++, fld = TREE_CHAIN(fld)) {
169                                 tree fieldtype;
170
171                                 fieldtype = TREE_TYPE(fld);
172                                 if (TREE_CODE(fieldtype) == INTEGER_TYPE)
173                                         continue;
174
175                                 *no_add_attrs = true;
176                                 error("structure variable %qD with %qE attribute has a non-integer field %qE",
177                                         *node, name, fld);
178                                 break;
179                         }
180
181                         if (fld)
182                                 break;
183
184 #if BUILDING_GCC_VERSION <= 4007
185                         vals = VEC_alloc(constructor_elt, gc, nelt);
186 #else
187                         vec_alloc(vals, nelt);
188 #endif
189
190                         for (fld = lst; fld; fld = TREE_CHAIN(fld)) {
191                                 tree random_const, fld_t = TREE_TYPE(fld);
192
193                                 random_const = tree_get_random_const(fld_t);
194                                 CONSTRUCTOR_APPEND_ELT(vals, fld, random_const);
195                         }
196
197                         /* Initialize the fields with random constants */
198                         DECL_INITIAL(*node) = build_constructor(type, vals);
199                         break;
200                 }
201
202                 /* Initialize the variable with a random constant */
203                 case INTEGER_TYPE:
204                         DECL_INITIAL(*node) = tree_get_random_const(type);
205                         break;
206
207                 case ARRAY_TYPE: {
208                         tree elt_type, array_size, elt_size;
209                         unsigned int i, nelt;
210                         HOST_WIDE_INT array_size_int, elt_size_int;
211
212                         elt_type = TREE_TYPE(type);
213                         elt_size = TYPE_SIZE_UNIT(TREE_TYPE(type));
214                         array_size = TYPE_SIZE_UNIT(type);
215
216                         if (TREE_CODE(elt_type) != INTEGER_TYPE || !array_size
217                                 || TREE_CODE(array_size) != INTEGER_CST) {
218                                 *no_add_attrs = true;
219                                 error("array variable %qD with %qE attribute must be a fixed length integer array type",
220                                         *node, name);
221                                 break;
222                         }
223
224                         array_size_int = TREE_INT_CST_LOW(array_size);
225                         elt_size_int = TREE_INT_CST_LOW(elt_size);
226                         nelt = array_size_int / elt_size_int;
227
228 #if BUILDING_GCC_VERSION <= 4007
229                         vals = VEC_alloc(constructor_elt, gc, nelt);
230 #else
231                         vec_alloc(vals, nelt);
232 #endif
233
234                         for (i = 0; i < nelt; i++) {
235                                 tree cst = size_int(i);
236                                 tree rand_cst = tree_get_random_const(elt_type);
237
238                                 CONSTRUCTOR_APPEND_ELT(vals, cst, rand_cst);
239                         }
240
241                         /*
242                          * Initialize the elements of the array with random
243                          * constants
244                          */
245                         DECL_INITIAL(*node) = build_constructor(type, vals);
246                         break;
247                 }
248                 }
249                 break;
250
251         case FUNCTION_DECL:
252                 break;
253         }
254
255         return NULL_TREE;
256 }
257
258 static struct attribute_spec latent_entropy_attr = {
259         .name                           = "latent_entropy",
260         .min_length                     = 0,
261         .max_length                     = 0,
262         .decl_required                  = true,
263         .type_required                  = false,
264         .function_type_required         = false,
265         .handler                        = handle_latent_entropy_attribute,
266 #if BUILDING_GCC_VERSION >= 4007
267         .affects_type_identity          = false
268 #endif
269 };
270
271 static void register_attributes(void *event_data __unused, void *data __unused)
272 {
273         register_attribute(&latent_entropy_attr);
274 }
275
276 static bool latent_entropy_gate(void)
277 {
278         tree list;
279
280         /* don't bother with noreturn functions for now */
281         if (TREE_THIS_VOLATILE(current_function_decl))
282                 return false;
283
284         /* gcc-4.5 doesn't discover some trivial noreturn functions */
285         if (EDGE_COUNT(EXIT_BLOCK_PTR_FOR_FN(cfun)->preds) == 0)
286                 return false;
287
288         list = DECL_ATTRIBUTES(current_function_decl);
289         return lookup_attribute("latent_entropy", list) != NULL_TREE;
290 }
291
292 static tree create_var(tree type, const char *name)
293 {
294         tree var;
295
296         var = create_tmp_var(type, name);
297         add_referenced_var(var);
298         mark_sym_for_renaming(var);
299         return var;
300 }
301
302 /*
303  * Set up the next operation and its constant operand to use in the latent
304  * entropy PRNG. When RHS is specified, the request is for perturbing the
305  * local latent entropy variable, otherwise it is for perturbing the global
306  * latent entropy variable where the two operands are already given by the
307  * local and global latent entropy variables themselves.
308  *
309  * The operation is one of add/xor/rol when instrumenting the local entropy
310  * variable and one of add/xor when perturbing the global entropy variable.
311  * Rotation is not used for the latter case because it would transmit less
312  * entropy to the global variable than the other two operations.
313  */
314 static enum tree_code get_op(tree *rhs)
315 {
316         static enum tree_code op;
317         unsigned HOST_WIDE_INT random_const;
318
319         random_const = get_random_const();
320
321         switch (op) {
322         case BIT_XOR_EXPR:
323                 op = PLUS_EXPR;
324                 break;
325
326         case PLUS_EXPR:
327                 if (rhs) {
328                         op = LROTATE_EXPR;
329                         /*
330                          * This code limits the value of random_const to
331                          * the size of a long for the rotation
332                          */
333                         random_const %= TYPE_PRECISION(long_unsigned_type_node);
334                         break;
335                 }
336
337         case LROTATE_EXPR:
338         default:
339                 op = BIT_XOR_EXPR;
340                 break;
341         }
342         if (rhs)
343                 *rhs = build_int_cstu(long_unsigned_type_node, random_const);
344         return op;
345 }
346
347 static gimple create_assign(enum tree_code code, tree lhs, tree op1,
348                                 tree op2)
349 {
350         return gimple_build_assign_with_ops(code, lhs, op1, op2);
351 }
352
353 static void perturb_local_entropy(basic_block bb, tree local_entropy)
354 {
355         gimple_stmt_iterator gsi;
356         gimple assign;
357         tree rhs;
358         enum tree_code op;
359
360         op = get_op(&rhs);
361         assign = create_assign(op, local_entropy, local_entropy, rhs);
362         gsi = gsi_after_labels(bb);
363         gsi_insert_before(&gsi, assign, GSI_NEW_STMT);
364         update_stmt(assign);
365 }
366
367 static void __perturb_latent_entropy(gimple_stmt_iterator *gsi,
368                                         tree local_entropy)
369 {
370         gimple assign;
371         tree temp;
372         enum tree_code op;
373
374         /* 1. create temporary copy of latent_entropy */
375         temp = create_var(long_unsigned_type_node, "temp_latent_entropy");
376
377         /* 2. read... */
378         add_referenced_var(latent_entropy_decl);
379         mark_sym_for_renaming(latent_entropy_decl);
380         assign = gimple_build_assign(temp, latent_entropy_decl);
381         gsi_insert_before(gsi, assign, GSI_NEW_STMT);
382         update_stmt(assign);
383
384         /* 3. ...modify... */
385         op = get_op(NULL);
386         assign = create_assign(op, temp, temp, local_entropy);
387         gsi_insert_after(gsi, assign, GSI_NEW_STMT);
388         update_stmt(assign);
389
390         /* 4. ...write latent_entropy */
391         assign = gimple_build_assign(latent_entropy_decl, temp);
392         gsi_insert_after(gsi, assign, GSI_NEW_STMT);
393         update_stmt(assign);
394 }
395
396 static bool handle_tail_calls(basic_block bb, tree local_entropy)
397 {
398         gimple_stmt_iterator gsi;
399
400         for (gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) {
401                 gcall *call;
402                 gimple stmt = gsi_stmt(gsi);
403
404                 if (!is_gimple_call(stmt))
405                         continue;
406
407                 call = as_a_gcall(stmt);
408                 if (!gimple_call_tail_p(call))
409                         continue;
410
411                 __perturb_latent_entropy(&gsi, local_entropy);
412                 return true;
413         }
414
415         return false;
416 }
417
418 static void perturb_latent_entropy(tree local_entropy)
419 {
420         edge_iterator ei;
421         edge e, last_bb_e;
422         basic_block last_bb;
423
424         gcc_assert(single_pred_p(EXIT_BLOCK_PTR_FOR_FN(cfun)));
425         last_bb_e = single_pred_edge(EXIT_BLOCK_PTR_FOR_FN(cfun));
426
427         FOR_EACH_EDGE(e, ei, last_bb_e->src->preds) {
428                 if (ENTRY_BLOCK_PTR_FOR_FN(cfun) == e->src)
429                         continue;
430                 if (EXIT_BLOCK_PTR_FOR_FN(cfun) == e->src)
431                         continue;
432
433                 handle_tail_calls(e->src, local_entropy);
434         }
435
436         last_bb = single_pred(EXIT_BLOCK_PTR_FOR_FN(cfun));
437         if (!handle_tail_calls(last_bb, local_entropy)) {
438                 gimple_stmt_iterator gsi = gsi_last_bb(last_bb);
439
440                 __perturb_latent_entropy(&gsi, local_entropy);
441         }
442 }
443
444 static void init_local_entropy(basic_block bb, tree local_entropy)
445 {
446         gimple assign, call;
447         tree frame_addr, rand_const, tmp, fndecl, udi_frame_addr;
448         enum tree_code op;
449         unsigned HOST_WIDE_INT rand_cst;
450         gimple_stmt_iterator gsi = gsi_after_labels(bb);
451
452         /* 1. create local_entropy_frameaddr */
453         frame_addr = create_var(ptr_type_node, "local_entropy_frameaddr");
454
455         /* 2. local_entropy_frameaddr = __builtin_frame_address() */
456         fndecl = builtin_decl_implicit(BUILT_IN_FRAME_ADDRESS);
457         call = gimple_build_call(fndecl, 1, integer_zero_node);
458         gimple_call_set_lhs(call, frame_addr);
459         gsi_insert_before(&gsi, call, GSI_NEW_STMT);
460         update_stmt(call);
461
462         udi_frame_addr = fold_convert(long_unsigned_type_node, frame_addr);
463         assign = gimple_build_assign(local_entropy, udi_frame_addr);
464         gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
465         update_stmt(assign);
466
467         /* 3. create temporary copy of latent_entropy */
468         tmp = create_var(long_unsigned_type_node, "temp_latent_entropy");
469
470         /* 4. read the global entropy variable into local entropy */
471         add_referenced_var(latent_entropy_decl);
472         mark_sym_for_renaming(latent_entropy_decl);
473         assign = gimple_build_assign(tmp, latent_entropy_decl);
474         gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
475         update_stmt(assign);
476
477         /* 5. mix local_entropy_frameaddr into local entropy */
478         assign = create_assign(BIT_XOR_EXPR, local_entropy, local_entropy, tmp);
479         gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
480         update_stmt(assign);
481
482         rand_cst = get_random_const();
483         rand_const = build_int_cstu(long_unsigned_type_node, rand_cst);
484         op = get_op(NULL);
485         assign = create_assign(op, local_entropy, local_entropy, rand_const);
486         gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
487         update_stmt(assign);
488 }
489
490 static bool create_latent_entropy_decl(void)
491 {
492         varpool_node_ptr node;
493
494         if (latent_entropy_decl != NULL_TREE)
495                 return true;
496
497         FOR_EACH_VARIABLE(node) {
498                 tree name, var = NODE_DECL(node);
499
500                 if (DECL_NAME_LENGTH(var) < sizeof("latent_entropy") - 1)
501                         continue;
502
503                 name = DECL_NAME(var);
504                 if (strcmp(IDENTIFIER_POINTER(name), "latent_entropy"))
505                         continue;
506
507                 latent_entropy_decl = var;
508                 break;
509         }
510
511         return latent_entropy_decl != NULL_TREE;
512 }
513
514 static unsigned int latent_entropy_execute(void)
515 {
516         basic_block bb;
517         tree local_entropy;
518
519         if (!create_latent_entropy_decl())
520                 return 0;
521
522         /* prepare for step 2 below */
523         gcc_assert(single_succ_p(ENTRY_BLOCK_PTR_FOR_FN(cfun)));
524         bb = single_succ(ENTRY_BLOCK_PTR_FOR_FN(cfun));
525         if (!single_pred_p(bb)) {
526                 split_edge(single_succ_edge(ENTRY_BLOCK_PTR_FOR_FN(cfun)));
527                 gcc_assert(single_succ_p(ENTRY_BLOCK_PTR_FOR_FN(cfun)));
528                 bb = single_succ(ENTRY_BLOCK_PTR_FOR_FN(cfun));
529         }
530
531         /* 1. create the local entropy variable */
532         local_entropy = create_var(long_unsigned_type_node, "local_entropy");
533
534         /* 2. initialize the local entropy variable */
535         init_local_entropy(bb, local_entropy);
536
537         bb = bb->next_bb;
538
539         /*
540          * 3. instrument each BB with an operation on the
541          *    local entropy variable
542          */
543         while (bb != EXIT_BLOCK_PTR_FOR_FN(cfun)) {
544                 perturb_local_entropy(bb, local_entropy);
545                 bb = bb->next_bb;
546         };
547
548         /* 4. mix local entropy into the global entropy variable */
549         perturb_latent_entropy(local_entropy);
550         return 0;
551 }
552
553 static void latent_entropy_start_unit(void *gcc_data __unused,
554                                         void *user_data __unused)
555 {
556         tree type, id;
557         int quals;
558
559         seed = get_random_seed(false);
560
561         if (in_lto_p)
562                 return;
563
564         /* extern volatile unsigned long latent_entropy */
565         quals = TYPE_QUALS(long_unsigned_type_node) | TYPE_QUAL_VOLATILE;
566         type = build_qualified_type(long_unsigned_type_node, quals);
567         id = get_identifier("latent_entropy");
568         latent_entropy_decl = build_decl(UNKNOWN_LOCATION, VAR_DECL, id, type);
569
570         TREE_STATIC(latent_entropy_decl) = 1;
571         TREE_PUBLIC(latent_entropy_decl) = 1;
572         TREE_USED(latent_entropy_decl) = 1;
573         DECL_PRESERVE_P(latent_entropy_decl) = 1;
574         TREE_THIS_VOLATILE(latent_entropy_decl) = 1;
575         DECL_EXTERNAL(latent_entropy_decl) = 1;
576         DECL_ARTIFICIAL(latent_entropy_decl) = 1;
577         lang_hooks.decls.pushdecl(latent_entropy_decl);
578 }
579
580 #define PASS_NAME latent_entropy
581 #define PROPERTIES_REQUIRED PROP_gimple_leh | PROP_cfg
582 #define TODO_FLAGS_FINISH TODO_verify_ssa | TODO_verify_stmts | TODO_dump_func \
583         | TODO_update_ssa
584 #include "gcc-generate-gimple-pass.h"
585
586 __visible int plugin_init(struct plugin_name_args *plugin_info,
587                           struct plugin_gcc_version *version)
588 {
589         bool enabled = true;
590         const char * const plugin_name = plugin_info->base_name;
591         const int argc = plugin_info->argc;
592         const struct plugin_argument * const argv = plugin_info->argv;
593         int i;
594
595         static const struct ggc_root_tab gt_ggc_r_gt_latent_entropy[] = {
596                 {
597                         .base = &latent_entropy_decl,
598                         .nelt = 1,
599                         .stride = sizeof(latent_entropy_decl),
600                         .cb = &gt_ggc_mx_tree_node,
601                         .pchw = &gt_pch_nx_tree_node
602                 },
603                 LAST_GGC_ROOT_TAB
604         };
605
606         PASS_INFO(latent_entropy, "optimized", 1, PASS_POS_INSERT_BEFORE);
607
608         if (!plugin_default_version_check(version, &gcc_version)) {
609                 error(G_("incompatible gcc/plugin versions"));
610                 return 1;
611         }
612
613         for (i = 0; i < argc; ++i) {
614                 if (!(strcmp(argv[i].key, "disable"))) {
615                         enabled = false;
616                         continue;
617                 }
618                 error(G_("unknown option '-fplugin-arg-%s-%s'"), plugin_name, argv[i].key);
619         }
620
621         register_callback(plugin_name, PLUGIN_INFO, NULL,
622                                 &latent_entropy_plugin_info);
623         if (enabled) {
624                 register_callback(plugin_name, PLUGIN_START_UNIT,
625                                         &latent_entropy_start_unit, NULL);
626                 register_callback(plugin_name, PLUGIN_REGISTER_GGC_ROOTS,
627                                   NULL, (void *)&gt_ggc_r_gt_latent_entropy);
628                 register_callback(plugin_name, PLUGIN_PASS_MANAGER_SETUP, NULL,
629                                         &latent_entropy_pass_info);
630         }
631         register_callback(plugin_name, PLUGIN_ATTRIBUTES, register_attributes,
632                                 NULL);
633
634         return 0;
635 }