sim.c

   1 #define _GNU_SOURCE
   2 #include<assert.h>
   3 #include<sched.h>
   4 #include<signal.h>
   5 #include<stdio.h>
   6 #include<stdlib.h>
   7 #include<time.h>
   8 #include<unistd.h>
   9 #include<sys/wait.h>
  10
  11 #include<pthread.h>
  12
  13 /* magic value to indicate upstream is dead */
  14 #define UART_DEAD 2
  15
  16 /* only relevant instructions */
  17 #define INSTR_NOP 0
  18 #define INSTR_ROUTE 4
  19
  20 /* Doing nothing, waiting for an instruction */
  21 #define STATE_IDLE 0
  22 #define STATE_READ_INSTRUCTION 10
  23 #define STATE_READ_NEWS_ADDRESS 20
  24 #define STATE_READ_NEWS_DATA 30
  25 /* Propagating the last received instruction
  26   (or waiting for neighbour to be ready so I can propagate) */
  27 #define STATE_PROPAGATE 1
  28 #define STATE_PROPAGATE2 11
  29 /* Executing some instruction */
  30 #define STATE_EXECUTE 2
  31 /* Sending NEWS to neighbour
  32    (or waiting for neighbour to be ready so I can send) */
  33 #define STATE_NEWS 3
  34 #define STATE_NEWS2 13
  35 #define STATE_NEWS3 23
  36
  37 // UART encoding is: to send the byte [b] we write [b * 2 + 1] in the
  38 // given location, then on the next cycle we write 0.
  39
  40 static void wait_cycles(int cycles) {
  41         struct timespec ts;
  42         long millis = 200;
  43         millis += (long)(rand() % 100 - 50);
  44         millis *= cycles;
  45         ts.tv_sec = millis / 1000;
  46         ts.tv_nsec = (millis % 1000) * 100000;
  47         nanosleep(&ts, NULL);
  48 }
  49
  50 /* sleep for 150-250ms */
  51 static void wait_one_cycle(void) {
  52         wait_cycles(1);
  53 }
  54
  55 #define BLOG_THREAD_STARTED    0
  56 #define BLOG_UART_BAD_KIND     1
  57 #define BLOG_READ_INSTRUCTION  2
  58 #define BLOG_READ_NEWS_ADDRESS 3
  59 #define BLOG_READ_NEWS_DATA    4
  60 #define BLOG_BECAME_NOT_READY  5
  61 #define BLOG_INVALID_STATE     6
  62 #define BLOG_EXECUTED_INSTR    7
  63 #define BLOG_MANUFACTURED_INSTRUCTION 8
  64 #define BLOG_READ_KIND 9
  65 #define BLOG_TRY_SENDING_NEWS 10
  66 #define BLOG_DONE_SENDING_NEWS 11
  67
  68 const char *blog_what[] = {
  69         "thread started",
  70         "uart bad kind",
  71         "read instruction",
  72         "read news address",
  73         "read news data",
  74         "ERROR: downstream became not ready!",
  75         "ERROR: invalid state",
  76         "executed instruction",
  77         "manufactured instruction",
  78         "read kind from uart",
  79         "trying to send news",
  80         "finished sending news",
  81 };
  82
  83 struct blog {
  84         int who;
  85         int what;
  86         int data;
  87 };
  88
  89 static volatile struct blog blog[1000];
  90 static volatile int blog_n = 0;
  91
  92 void display_post(int i) {
  93         printf("\033[3%dm%d: %s (%d)\033[0m\n", blog[i].who + 1, blog[i].who, blog_what[blog[i].what], blog[i].data);
  94 }
  95
  96 void post(int who, int what, int data) {
  97         int idx = blog_n++;
  98         blog[idx].who = who;
  99         blog[idx].what = what;
 100         blog[idx].data = data;
 101         display_post(idx);
 102 }
 103
 104 #define POST(what, data) post(id, what, data)
 105
 106 int uart_data(int x) {
 107         return 2 * x + 1;
 108 }
 109
 110 static void tx(volatile int *uart_tx, int data) {
 111         *uart_tx = data;
 112         wait_cycles(5);
 113 //      assert(*uart_tx == 0);
 114 }
 115
 116 #define TX(data) tx(uart_tx, uart_data(data))
 117 #define KILL_UART() tx(uart_tx, 2)
 118
 119 static int rx(volatile int *uart_rx) {
 120         int read = *uart_rx;
 121         *uart_rx = 0;
 122         return read;
 123 }
 124
 125 #define RX() rx(uart_rx)
 126
 127 void worker(int id, volatile int *uart_tx, volatile int *uart_rx, volatile int *ready_out, volatile const int *ready_in){
 128         int current_instr = 0;
 129
 130         int state = STATE_IDLE;
 131         *ready_out = 1;
 132         *uart_tx = 0;
 133         POST(BLOG_THREAD_STARTED, 0);
 134
 135         int read, kind, instruction, address, data;
 136
 137         while(1) {
 138                 switch(state) {
 139                 case STATE_IDLE:
 140                         read = RX();
 141                         wait_one_cycle();
 142                         if(read == 2) { // upstream dead!
 143                                 KILL_UART();
 144                                 return;
 145                         }
 146                         if(!read) /* nothing on uart */
 147                                 break;
 148                         kind = read >> 1;
 149                         POST(BLOG_READ_KIND, kind);
 150                         if(kind == 1)
 151                                 state = STATE_READ_INSTRUCTION;
 152                         else if(kind == 2)
 153                                 state = STATE_READ_NEWS_ADDRESS;
 154                         else
 155                                 POST(BLOG_UART_BAD_KIND, kind);
 156                         break;
 157
 158                 case STATE_READ_INSTRUCTION:
 159                         read = RX();
 160                         wait_one_cycle();
 161                         if(!read) /* nothing on uart */
 162                                 break;
 163                         instruction = read >> 1;
 164                         current_instr = instruction;
 165                         *ready_out = 0;
 166                         POST(BLOG_READ_INSTRUCTION, instruction);
 167                         state = STATE_PROPAGATE;
 168                         break;
 169
 170                 case STATE_READ_NEWS_ADDRESS:
 171                         read = RX();
 172                         wait_one_cycle();
 173                         if(!read) /* nothing on uart */
 174                                 break;
 175                         address = read >> 1;
 176                         current_instr = address;
 177                         POST(BLOG_READ_NEWS_ADDRESS, address);
 178                         state = STATE_READ_NEWS_DATA;
 179                         break;
 180
 181                 case STATE_READ_NEWS_DATA:
 182                         read = RX();
 183                         wait_one_cycle();
 184                         if(!read) /* nothing on uart */
 185                                 break;
 186                         data = read >> 1;
 187                         /* we now have the address in [current_instr] and data in [data].
 188                            We write a NOP instruction because we have no memory. */
 189                         current_instr = INSTR_NOP;
 190                         *ready_out = 0;
 191                         POST(BLOG_READ_NEWS_DATA, data);
 192                         state = STATE_EXECUTE;
 193                         break;
 194
 195                 case STATE_PROPAGATE:
 196                         if(!*ready_in)
 197                                 break;
 198                         TX(1); /* we're writing an instruction */
 199                         state = STATE_PROPAGATE2;
 200                         break;
 201
 202                 case STATE_PROPAGATE2:
 203                         if(!*ready_in) {
 204                                 POST(BLOG_BECAME_NOT_READY, state);
 205                                 state = STATE_PROPAGATE;
 206                                 break;
 207                         }
 208                         TX(current_instr);
 209                         state = STATE_EXECUTE;
 210                         break;
 211
 212                 case STATE_EXECUTE:
 213                         wait_one_cycle(); // execution takes time! (not really)
 214                         if(current_instr == INSTR_ROUTE) {
 215                                 state = STATE_NEWS;
 216                                 POST(BLOG_EXECUTED_INSTR, current_instr);
 217 //                              POST(BLOG_TRY_SENDING_NEWS, 0);
 218                         } else {
 219                                 state = STATE_IDLE;
 220                                 *ready_out = 1;
 221                                 POST(BLOG_EXECUTED_INSTR, current_instr);
 222                         }
 223                         break;
 224
 225                 case STATE_NEWS:
 226                         if(!*ready_in)
 227                                 break;
 228                         TX(2);
 229                         state = STATE_NEWS2;
 230                         break;
 231
 232                 case STATE_NEWS2:
 233                         if(!*ready_in) {
 234                                 POST(BLOG_BECAME_NOT_READY, state);
 235                                 state = STATE_NEWS;
 236                                 break;
 237                         }
 238                         TX(rand() & 0xFF);
 239                         state = STATE_NEWS3;
 240                         break;
 241
 242                 case STATE_NEWS3:
 243                         if(!*ready_in) {
 244                                 POST(BLOG_BECAME_NOT_READY, state);
 245                                 state = STATE_NEWS;
 246                                 break;
 247                         }
 248                         TX(rand() & 0xFF);
 249                         state = STATE_IDLE;
 250                         *ready_out = 1;
 251 //                      POST(BLOG_DONE_SENDING_NEWS, 0);
 252                         break;
 253
 254                 default:
 255                         POST(BLOG_INVALID_STATE, state);
 256                         break;
 257                 }
 258                 wait_one_cycle();
 259         }
 260 }
 261
 262 #define MASTER_SEND_INSTRUCTION 0
 263 #define MASTER_SEND_INSTRUCTION2 10
 264 #define MASTER_WAIT_FOR_NEWS 1
 265 #define MASTER_READ_NEWS_ADDRESS 11
 266 #define MASTER_READ_NEWS_DATA 21
 267 #define MASTER_WAIT_FOR_PROPAGATE 2
 268 #define MASTER_WAIT_FOR_PROPAGATE2 12
 269
 270 void master(volatile int *uart_tx, volatile int *uart_rx, volatile int *ready_out, volatile const int *ready_in){
 271         int instructions_left = 10;
 272         int state = MASTER_SEND_INSTRUCTION;
 273         int ignore_next_rx = 0;
 274         const int id = 0;
 275         int read, kind, instruction, data, rnd;
 276
 277         *uart_tx = 0;
 278         *ready_out = 1;
 279         POST(BLOG_THREAD_STARTED, 0);
 280
 281         while(1) {
 282                 switch(state) {
 283                 case MASTER_SEND_INSTRUCTION:
 284                         if(!instructions_left) { /* done! */
 285                                 KILL_UART();
 286                                 return;
 287                         }
 288                         if(!*ready_in)
 289                                 break;
 290                         TX(1);
 291                         state = MASTER_SEND_INSTRUCTION2;
 292                         break;
 293
 294                 case MASTER_SEND_INSTRUCTION2:
 295                         if(!*ready_in) {
 296                                 POST(BLOG_BECAME_NOT_READY, state);
 297                                 state = MASTER_SEND_INSTRUCTION;
 298                                 break;
 299                         }
 300                         /* manufacture an instruction */
 301                         rnd = rand() & 7;
 302                         if(rnd <= 4)
 303                                 instruction = INSTR_NOP;
 304                         else if(rnd <= 6)
 305                                 instruction = INSTR_ROUTE;
 306                         else
 307                                 instruction = INSTR_ROUTE; /* actually READ */
 308
 309                         POST(BLOG_MANUFACTURED_INSTRUCTION, rnd);
 310                         TX(instruction);
 311                         instructions_left--;
 312
 313                         if(instruction == INSTR_ROUTE)
 314                                 state = MASTER_WAIT_FOR_NEWS;
 315                         else
 316                                 state = MASTER_WAIT_FOR_PROPAGATE;
 317                         break;
 318
 319                 case MASTER_WAIT_FOR_PROPAGATE:
 320                         read = RX();
 321                         wait_one_cycle();
 322                         if(!read) /* nothing on uart */
 323                                 break;
 324                         kind = read >> 1;
 325                         if(kind == 1)
 326                                 state = MASTER_WAIT_FOR_PROPAGATE2;
 327                         else /* kind == 2 is also bad here */
 328                                 POST(BLOG_UART_BAD_KIND, kind);
 329                         break;
 330
 331                 case MASTER_WAIT_FOR_PROPAGATE2:
 332                         read = RX();
 333                         wait_one_cycle();
 334                         if(!read) /* nothing on uart */
 335                                 break;
 336                         instruction = read >> 1; /* we don't care about this */
 337                         state = MASTER_SEND_INSTRUCTION;
 338                         break;
 339
 340                 case MASTER_WAIT_FOR_NEWS:
 341                         read = RX();
 342                         wait_one_cycle();
 343                         if(!read) /* nothing on uart */
 344                                 break;
 345                         kind = read >> 1;
 346                         if(ignore_next_rx)
 347                                 ignore_next_rx = 0;
 348                         else if(kind == 1) /* propagation, ignore next byte */
 349                                 ignore_next_rx = 1;
 350                         else if(kind == 2) { /* ka-ching! */
 351                                 state = MASTER_READ_NEWS_ADDRESS;
 352                         } else
 353                                 POST(BLOG_UART_BAD_KIND, kind);
 354                         break;
 355
 356                 case MASTER_READ_NEWS_ADDRESS:
 357                         read = RX();
 358                         wait_one_cycle();
 359                         if(!read) /* nothing on uart */
 360                                 break;
 361                         /* we do not care about the address, we go read the data */
 362                         state = MASTER_READ_NEWS_DATA;
 363                         break;
 364
 365                 case MASTER_READ_NEWS_DATA:
 366                         read = RX();
 367                         wait_one_cycle();
 368                         if(!read) /* nothing on uart */
 369                                 break;
 370                         data = read >> 1;
 371                         POST(BLOG_READ_NEWS_DATA, data);
 372                         state = MASTER_SEND_INSTRUCTION;
 373                         break;
 374
 375                 default:
 376                         POST(BLOG_INVALID_STATE, state);
 377                         break;
 378                 }
 379                 wait_one_cycle();
 380         }
 381         KILL_UART();
 382 }
 383
 384 static int uarts[5];
 385 static int ready[5];
 386 static pthread_t threads[5];
 387
 388 void* spawn_thread(void* index) {
 389         switch((long)index) {
 390         case 0:
 391                 master(uarts + 0, uarts + 4, ready + 4, ready + 0);
 392                 break;
 393         case 1:
 394                 worker(1, uarts + 1, uarts + 0, ready + 0, ready + 1);
 395                 break;
 396         case 2:
 397                 worker(2, uarts + 2, uarts + 1, ready + 1, ready + 2);
 398                 break;
 399         case 3:
 400                 worker(3, uarts + 3, uarts + 2, ready + 2, ready + 3);
 401                 break;
 402         case 4:
 403                 worker(4, uarts + 4, uarts + 3, ready + 3, ready + 4);
 404                 break;
 405         default:
 406                 printf("Spawned bad thread %ld\n", (long)index);
 407         }
 408         return NULL;
 409 }
 410
 411 int main(void){
 412         for(long i = 0 ; i < 5 ; i++)
 413                 pthread_create(threads + i, NULL, spawn_thread, (void*)i);
 414         for(int i = 0 ; i < 5 ; i++)
 415                 pthread_join(threads[i], NULL);
 416 //      for(int i = 0; i < blog_n; i++)
 417 //              display_post(i);
 418         return 0;
 419 }