src/binaryen/scripts/fuzz_relooper.py

   1 #! /usr/bin/env python
   2
   3 #   Copyright 2016 WebAssembly Community Group participants
   4 #
   5 #   Licensed under the Apache License, Version 2.0 (the "License");
   6 #   you may not use this file except in compliance with the License.
   7 #   You may obtain a copy of the License at
   8 #
   9 #       http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 #   Unless required by applicable law or agreed to in writing, software
  12 #   distributed under the License is distributed on an "AS IS" BASIS,
  13 #   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 #   See the License for the specific language governing permissions and
  15 #   limitations under the License.
  16
  17 '''
  18 This fuzzes the relooper using the C API.
  19 '''
  20
  21 import difflib
  22 import os
  23 import random
  24 import subprocess
  25
  26 if os.environ.get('LD_LIBRARY_PATH'):
  27   os.environ['LD_LIBRARY_PATH'] += os.pathsep + 'lib'
  28 else:
  29   os.environ['LD_LIBRARY_PATH'] = 'lib'
  30
  31 counter = 0
  32
  33 while True:
  34   # Random decisions
  35   num = random.randint(2, 250)
  36   density = random.random() * random.random()
  37   max_decision = num * 20
  38   decisions = [random.randint(1, max_decision) for x in range(num * 3)]
  39   branches = [0] * num
  40   defaults = [0] * num
  41   for i in range(num):
  42     b = set([])
  43     bs = random.randint(1, max(1,
  44                                round(density * random.random() * (num - 1))))
  45     for j in range(bs):
  46       b.add(random.randint(1, num - 1))
  47     b = list(b)
  48     defaults[i] = random.choice(b)
  49     b.remove(defaults[i])
  50     branches[i] = b
  51   optimize = random.random() < 0.5
  52   print counter, ':', num, density, optimize
  53   counter += 1
  54
  55   for temp in ['fuzz.wasm', 'fuzz.wast', 'fast.txt', 'fuzz.slow.js',
  56                'fuzz.c']:
  57     try:
  58       os.unlink(temp)
  59     except OSError:
  60       pass
  61
  62   # parts
  63   entry = '''
  64 var label = 0;
  65 var state;
  66 var decisions = %s;
  67 var index = 0;
  68 function check() {
  69   if (index == decisions.length) throw 'HALT';
  70   console.log('(i32.const ' + (-decisions[index]) + ')');
  71   return decisions[index++];
  72 }
  73 ''' % str(decisions)
  74
  75   slow = entry + '\n'
  76   slow += 'label = 0;\n'
  77
  78   slow += '''
  79 while(1) switch(label) {
  80 '''
  81
  82   fast = '''
  83
  84 #include <assert.h>
  85 #include <stdio.h>
  86
  87 #include "binaryen-c.h"
  88
  89 // globals: address 4 is index
  90 // decisions are at address 8+
  91
  92 int main() {
  93   BinaryenModuleRef module = BinaryenModuleCreate();
  94
  95   // check()
  96
  97   // if the end, halt
  98   BinaryenExpressionRef halter = BinaryenIf(module,
  99     BinaryenBinary(module,
 100       BinaryenEqInt32(),
 101       BinaryenLoad(module, 4, 0, 0, 0, BinaryenInt32(),
 102                    BinaryenConst(module, BinaryenLiteralInt32(4))),
 103       BinaryenConst(module, BinaryenLiteralInt32(4 * %d)) // jumps of 4 bytes
 104     ),
 105     BinaryenUnreachable(module),
 106     NULL
 107   );
 108   // increment index
 109   BinaryenExpressionRef incer = BinaryenStore(module,
 110     4, 0, 0,
 111     BinaryenConst(module, BinaryenLiteralInt32(4)),
 112     BinaryenBinary(module,
 113       BinaryenAddInt32(),
 114       BinaryenLoad(module, 4, 0, 0, 0, BinaryenInt32(),
 115                    BinaryenConst(module, BinaryenLiteralInt32(4))),
 116       BinaryenConst(module, BinaryenLiteralInt32(4))
 117     ),
 118     BinaryenInt32()
 119   );
 120
 121   // optionally, print the return value
 122   BinaryenExpressionRef args[] = {
 123     BinaryenBinary(module,
 124       BinaryenSubInt32(),
 125       BinaryenConst(module, BinaryenLiteralInt32(0)),
 126       BinaryenLoad(module,
 127         4, 0, 4, 0, BinaryenInt32(),
 128         BinaryenLoad(module, 4, 0, 0, 0, BinaryenInt32(),
 129                      BinaryenConst(module, BinaryenLiteralInt32(4)))
 130       )
 131     )
 132   };
 133   BinaryenExpressionRef debugger;
 134   if (1) debugger = BinaryenCallImport(module, "print", args, 1,
 135                                        BinaryenNone());
 136   else debugger = BinaryenNop(module);
 137
 138   // return the decision. need to subtract 4 that we just added,
 139   // and add 8 since that's where we start, so overall offset 4
 140   BinaryenExpressionRef returner = BinaryenLoad(module,
 141     4, 0, 4, 0, BinaryenInt32(),
 142     BinaryenLoad(module, 4, 0, 0, 0, BinaryenInt32(),
 143     BinaryenConst(module, BinaryenLiteralInt32(4)))
 144   );
 145   BinaryenExpressionRef checkBodyList[] = { halter, incer, debugger,
 146                                             returner };
 147   BinaryenExpressionRef checkBody = BinaryenBlock(module,
 148     NULL, checkBodyList, sizeof(checkBodyList) / sizeof(BinaryenExpressionRef)
 149   );
 150   BinaryenFunctionTypeRef i = BinaryenAddFunctionType(module, "i",
 151                                                       BinaryenInt32(),
 152                                                       NULL, 0);
 153   BinaryenAddFunction(module, "check", i, NULL, 0, checkBody);
 154
 155   // contents of main() begin here
 156
 157   RelooperRef relooper = RelooperCreate();
 158
 159 ''' % len(decisions)
 160
 161   for i in range(0, num):
 162     slow += '  case %d: console.log("(i32.const %d)"); state = check(); \n' % (
 163             i, i)
 164     b = branches[i]
 165     for j in range(len(b)):
 166       slow += '    if (state %% %d == %d) { label = %d; break }\n' % (
 167               len(b) + 1, j, b[j])  # TODO: split range 1-n into these options
 168     slow += '    label = %d; break\n' % defaults[i]
 169
 170   use_switch = [random.random() < 0.5 for i in range(num)]
 171
 172   for i in range(num):
 173     fast += '''
 174   RelooperBlockRef b%d;
 175   {
 176     BinaryenExpressionRef args[] = {
 177       BinaryenConst(module, BinaryenLiteralInt32(%d))
 178     };
 179     BinaryenExpressionRef list[] = {
 180       BinaryenCallImport(module, "print", args, 1, BinaryenNone()),
 181       BinaryenSetLocal(module, 0, BinaryenCall(module, "check", NULL, 0,
 182                                                BinaryenInt32()))
 183     };
 184 ''' % (i, i)
 185     if use_switch[i]:
 186       fast += '''
 187     b%d = RelooperAddBlockWithSwitch(relooper,
 188       BinaryenBlock(module, NULL, list, 2),
 189       BinaryenBinary(module,
 190         BinaryenRemUInt32(),
 191         BinaryenGetLocal(module, 0, BinaryenInt32()),
 192         BinaryenConst(module, BinaryenLiteralInt32(%d))
 193       )
 194     );
 195 ''' % (i, len(branches[i]) + 1)
 196     else:  # non-switch
 197       fast += '''
 198     b%d = RelooperAddBlock(relooper, BinaryenBlock(module, NULL, list, 2));
 199 ''' % i
 200     fast += '''
 201   }
 202 '''
 203
 204   for i in range(num):
 205     b = branches[i]
 206     for j in range(len(b)):
 207       if use_switch[i]:
 208         total = len(b) + 1
 209         values = ','.join([str(x) for x in range(random.randint(len(b) + 1,
 210                            max_decision + 2)) if x % total == j])
 211         fast += '''
 212   {
 213     BinaryenIndex values[] = { %s };
 214     RelooperAddBranchForSwitch(b%d, b%d, values,
 215                                sizeof(values) / sizeof(BinaryenIndex), NULL);
 216   }
 217 ''' % (values, i, b[j])
 218       else:  # non-switch
 219         fast += '''
 220   RelooperAddBranch(b%d, b%d, BinaryenBinary(module,
 221     BinaryenEqInt32(),
 222     BinaryenBinary(module,
 223       BinaryenRemUInt32(),
 224       BinaryenGetLocal(module, 0, BinaryenInt32()),
 225       BinaryenConst(module, BinaryenLiteralInt32(%d))
 226     ),
 227     BinaryenConst(module, BinaryenLiteralInt32(%d))
 228   ), NULL);
 229 ''' % (i, b[j], len(b) + 1, j)
 230     # default branch
 231     if use_switch[i]:
 232       fast += '''
 233   RelooperAddBranchForSwitch(b%d, b%d, NULL, 0, NULL);
 234 ''' % (i, defaults[i])
 235     else:
 236       fast += '''
 237   RelooperAddBranch(b%d, b%d, NULL, NULL);
 238 ''' % (i, defaults[i])
 239
 240   fast += '''
 241   BinaryenExpressionRef body = RelooperRenderAndDispose(relooper, b0, 1,
 242                                                         module);
 243
 244   int decisions[] = { %s };
 245   int numDecisions = sizeof(decisions)/sizeof(int);
 246
 247   // write out all the decisions, then the body of the function
 248   BinaryenExpressionRef full[numDecisions + 1];
 249
 250   {
 251     int i;
 252     for (i = 0; i < numDecisions; i++) {
 253       full[i] = BinaryenStore(module,
 254         4, 0, 0,
 255         BinaryenConst(module, BinaryenLiteralInt32(8 + 4 * i)),
 256         BinaryenConst(module, BinaryenLiteralInt32(decisions[i])),
 257         BinaryenInt32()
 258       );
 259     }
 260   }
 261   full[numDecisions] = body;
 262   BinaryenExpressionRef all = BinaryenBlock(module, NULL, full,
 263                                             numDecisions + 1);
 264
 265   BinaryenFunctionTypeRef v = BinaryenAddFunctionType(module, "v",
 266                                                       BinaryenNone(),
 267                                                       NULL, 0);
 268   // locals: state, free-for-label
 269   BinaryenType localTypes[] = { BinaryenInt32(), BinaryenInt32() };
 270   BinaryenFunctionRef theMain = BinaryenAddFunction(module, "main", v,
 271                                                     localTypes, 2, all);
 272   BinaryenSetStart(module, theMain);
 273
 274   // import
 275
 276   BinaryenType iparams[] = { BinaryenInt32() };
 277   BinaryenFunctionTypeRef vi = BinaryenAddFunctionType(module, "vi",
 278                                                        BinaryenNone(),
 279                                                        iparams, 1);
 280   BinaryenAddImport(module, "print", "spectest", "print", vi);
 281
 282   // memory
 283   BinaryenSetMemory(module, 1, 1, "mem", NULL, NULL, NULL, 0);
 284
 285   // optionally, optimize
 286   if (%d) BinaryenModuleOptimize(module);
 287
 288   assert(BinaryenModuleValidate(module));
 289
 290   // write it out
 291
 292   BinaryenModulePrint(module);
 293
 294   BinaryenModuleDispose(module);
 295
 296   return 0;
 297 }
 298 ''' % (', '.join(map(str, decisions)), optimize)
 299
 300   slow += '}'
 301
 302   open('fuzz.slow.js', 'w').write(slow)
 303   open('fuzz.c', 'w').write(fast)
 304
 305   print '.'
 306   cmd = [os.environ.get('CC') or 'gcc', 'fuzz.c', '-Isrc',
 307          '-lbinaryen', '-lasmjs',
 308          '-lsupport', '-Llib/.', '-pthread', '-o', 'fuzz']
 309   subprocess.check_call(cmd)
 310   print '^'
 311   subprocess.check_call(['./fuzz'], stdout=open('fuzz.wast', 'w'))
 312   print '*'
 313   fast_out = subprocess.Popen(['bin/wasm-shell', 'fuzz.wast'],
 314                               stdout=subprocess.PIPE,
 315                               stderr=subprocess.PIPE).communicate()[0]
 316   print '-'
 317   slow_out = subprocess.Popen(['nodejs', 'fuzz.slow.js'],
 318                               stdout=subprocess.PIPE,
 319                               stderr=subprocess.PIPE).communicate()[0]
 320   print '_'
 321
 322   if slow_out != fast_out:
 323     print ''.join([a.rstrip() + '\n' for a in difflib.unified_diff(
 324           slow_out.split('\n'),
 325           fast_out.split('\n'),
 326           fromfile='slow',
 327           tofile='fast')])
 328     assert False