src/proto/slam.c

   1 #if 0
   2
   3 /*
   4  * IMPORTANT
   5  *
   6  * This file should be rewritten to avoid the use of a bitmap.  Our
   7  * buffer routines can cope with being handed blocks in an arbitrary
   8  * order, duplicate blocks, etc.  This code could be substantially
   9  * simplified by taking advantage of these features.
  10  *
  11  */
  12
  13 #define SLAM_PORT 10000
  14 #define SLAM_MULTICAST_IP ((239<<24)|(255<<16)|(1<<8)|(1<<0))
  15 #define SLAM_MULTICAST_PORT 10000
  16 #define SLAM_LOCAL_PORT 10000
  17
  18 /* Set the timeout intervals to at least 1 second so
  19  * on a 100Mbit ethernet can receive 10000 packets
  20  * in one second.
  21  *
  22  * The only case that is likely to trigger all of the nodes
  23  * firing a nack packet is a slow server.  The odds of this
  24  * happening could be reduced being slightly smarter and utilizing
  25  * the multicast channels for nacks.   But that only improves the odds
  26  * it doesn't improve the worst case.  So unless this proves to be
  27  * a common case having the control data going unicast should increase
  28  * the odds of the data not being dropped.
  29  *
  30  * When doing exponential backoff we increase just the timeout
  31  * interval and not the base to optimize for throughput.  This is only
  32  * expected to happen when the server is down.  So having some nodes
  33  * pinging immediately should get the transmission restarted quickly after a
  34  * server restart.  The host nic won't be to baddly swamped because of
  35  * the random distribution of the nodes.
  36  *
  37  */
  38 #define SLAM_INITIAL_MIN_TIMEOUT      (TICKS_PER_SEC/3)
  39 #define SLAM_INITIAL_TIMEOUT_INTERVAL (TICKS_PER_SEC)
  40 #define SLAM_BASE_MIN_TIMEOUT         (2*TICKS_PER_SEC)
  41 #define SLAM_BASE_TIMEOUT_INTERVAL    (4*TICKS_PER_SEC)
  42 #define SLAM_BACKOFF_LIMIT 5
  43 #define SLAM_MAX_RETRIES 20
  44
  45 /*** Packets Formats ***
  46  * Data Packet:
  47  *   transaction
  48  *   total bytes
  49  *   block size
  50  *   packet #
  51  *   data
  52  *
  53  * Status Request Packet
  54  *   transaction
  55  *   total bytes
  56  *   block size
  57  *
  58  * Status Packet
  59  *   received packets
  60  *   requested packets
  61  *   received packets
  62  *   requested packets
  63  *   ...
  64  *   received packets
  65  *   requested packtes
  66  *   0
  67  */
  68
  69 #define MAX_HDR (7 + 7 + 7) /* transaction, total size, block size */
  70 #define MIN_HDR (1 + 1 + 1) /* transactino, total size, block size */
  71
  72 #define MAX_SLAM_REQUEST MAX_HDR
  73 #define MIN_SLAM_REQUEST MIN_HDR
  74
  75 #define MIN_SLAM_DATA (MIN_HDR + 1)
  76
  77 static struct slam_nack {
  78         struct iphdr ip;
  79         struct udphdr udp;
  80         unsigned char data[ETH_MAX_MTU -
  81                 (sizeof(struct iphdr) + sizeof(struct udphdr))];
  82 } nack;
  83
  84 struct slam_state {
  85         unsigned char hdr[MAX_HDR];
  86         unsigned long hdr_len;
  87         unsigned long block_size;
  88         unsigned long total_bytes;
  89         unsigned long total_packets;
  90
  91         unsigned long received_packets;
  92
  93         struct buffer *buffer;
  94         unsigned char *image;
  95         unsigned char *bitmap;
  96 } state;
  97
  98
  99 static void init_slam_state(void)
 100 {
 101         state.hdr_len = sizeof(state.hdr);
 102         memset(state.hdr, 0, state.hdr_len);
 103         state.block_size = 0;
 104         state.total_packets = 0;
 105
 106         state.received_packets = 0;
 107
 108         state.image = 0;
 109         state.bitmap = 0;
 110 }
 111
 112 struct slam_info {
 113         struct sockaddr_in server;
 114         struct sockaddr_in local;
 115         struct sockaddr_in multicast;
 116         int sent_nack;
 117         struct buffer *buffer;
 118 };
 119
 120 #define SLAM_TIMEOUT 0
 121 #define SLAM_REQUEST 1
 122 #define SLAM_DATA    2
 123 static int await_slam(int ival __unused, void *ptr,
 124                       unsigned short ptype __unused, struct iphdr *ip,
 125                       struct udphdr *udp, struct tcphdr *tcp __unused)
 126 {
 127         struct slam_info *info = ptr;
 128         if (!udp) {
 129                 return 0;
 130         }
 131         /* I can receive two kinds of packets here, a multicast data packet,
 132          * or a unicast request for information
 133          */
 134         /* Check for a data request packet */
 135         if ((ip->dest.s_addr == arptable[ARP_CLIENT].ipaddr.s_addr) &&
 136                 (ntohs(udp->dest) == info->local.sin_port) &&
 137                 (nic.packetlen >=
 138                         ETH_HLEN +
 139                         sizeof(struct iphdr) +
 140                         sizeof(struct udphdr) +
 141                         MIN_SLAM_REQUEST)) {
 142                 return SLAM_REQUEST;
 143         }
 144         /* Check for a multicast data packet */
 145         if ((ip->dest.s_addr == info->multicast.sin_addr.s_addr) &&
 146                 (ntohs(udp->dest) == info->multicast.sin_port) &&
 147                 (nic.packetlen >=
 148                         ETH_HLEN +
 149                         sizeof(struct iphdr) +
 150                         sizeof(struct udphdr) +
 151                         MIN_SLAM_DATA)) {
 152                 return SLAM_DATA;
 153         }
 154 #if 0
 155         printf("#");
 156         printf("dest: %@ port: %d len: %d\n",
 157                 ip->dest.s_addr, ntohs(udp->dest), nic.packetlen);
 158 #endif
 159         return 0;
 160
 161 }
 162
 163 static int slam_encode(
 164         unsigned char **ptr, unsigned char *end, unsigned long value)
 165 {
 166         unsigned char *data = *ptr;
 167         int bytes;
 168         bytes = sizeof(value);
 169         while ((bytes > 0) && ((0xff & (value >> ((bytes -1)<<3))) == 0)) {
 170                 bytes--;
 171         }
 172         if (bytes <= 0) {
 173                 bytes = 1;
 174         }
 175         if (data + bytes >= end) {
 176                 return -1;
 177         }
 178         if ((0xe0 & (value >> ((bytes -1)<<3))) == 0) {
 179                 /* packed together */
 180                 *data = (bytes << 5) | (value >> ((bytes -1)<<3));
 181         } else {
 182                 bytes++;
 183                 *data = (bytes << 5);
 184         }
 185         bytes--;
 186         data++;
 187         while(bytes) {
 188                 *(data++) = 0xff & (value >> ((bytes -1)<<3));
 189                 bytes--;
 190         }
 191         *ptr = data;
 192         return 0;
 193 }
 194
 195 static int slam_skip(unsigned char **ptr, unsigned char *end)
 196 {
 197         int bytes;
 198         if (*ptr >= end) {
 199                 return -1;
 200         }
 201         bytes = ((**ptr) >> 5) & 7;
 202         if (bytes == 0) {
 203                 return -1;
 204         }
 205         if (*ptr + bytes >= end) {
 206                 return -1;
 207         }
 208         (*ptr) += bytes;
 209         return 0;
 210
 211 }
 212
 213 static unsigned long slam_decode(unsigned char **ptr, unsigned char *end,
 214                                  int *err)
 215 {
 216         unsigned long value;
 217         unsigned bytes;
 218         if (*ptr >= end) {
 219                 *err = -1;
 220         }
 221         bytes = ((**ptr) >> 5) & 7;
 222         if ((bytes == 0) || (bytes > sizeof(unsigned long))) {
 223                 *err = -1;
 224                 return 0;
 225         }
 226         if ((*ptr) + bytes >= end) {
 227                 *err =  -1;
 228         }
 229         value = (**ptr) & 0x1f;
 230         bytes--;
 231         (*ptr)++;
 232         while(bytes) {
 233                 value <<= 8;
 234                 value |= **ptr;
 235                 (*ptr)++;
 236                 bytes--;
 237         }
 238         return value;
 239 }
 240
 241
 242 static long slam_sleep_interval(int exp)
 243 {
 244         long range;
 245         long divisor;
 246         long interval;
 247         range = SLAM_BASE_TIMEOUT_INTERVAL;
 248         if (exp < 0) {
 249                 divisor = RAND_MAX/SLAM_INITIAL_TIMEOUT_INTERVAL;
 250         } else {
 251                 if (exp > SLAM_BACKOFF_LIMIT)
 252                         exp = SLAM_BACKOFF_LIMIT;
 253                 divisor = RAND_MAX/(range << exp);
 254         }
 255         interval = random()/divisor;
 256         if (exp < 0) {
 257                 interval += SLAM_INITIAL_MIN_TIMEOUT;
 258         } else {
 259                 interval += SLAM_BASE_MIN_TIMEOUT;
 260         }
 261         return interval;
 262 }
 263
 264
 265 static unsigned char *reinit_slam_state(
 266         unsigned char *header, unsigned char *end)
 267 {
 268         unsigned long total_bytes;
 269         unsigned long block_size;
 270
 271         unsigned long bitmap_len;
 272         unsigned long max_packet_len;
 273         unsigned char *data;
 274         int err;
 275
 276 #if 0
 277         printf("reinit\n");
 278 #endif
 279         data = header;
 280
 281         state.hdr_len = 0;
 282         err = slam_skip(&data, end); /* transaction id */
 283         total_bytes = slam_decode(&data, end, &err);
 284         block_size  = slam_decode(&data, end, &err);
 285         if (err) {
 286                 printf("ALERT: slam size out of range\n");
 287                 return 0;
 288         }
 289         state.block_size = block_size;
 290         state.total_bytes = total_bytes;
 291         state.total_packets = (total_bytes + block_size - 1)/block_size;
 292         state.hdr_len = data - header;
 293         state.received_packets = 0;
 294
 295         data = state.hdr;
 296         slam_encode(&data, &state.hdr[sizeof(state.hdr)], state.total_packets);
 297         max_packet_len = data - state.hdr;
 298         memcpy(state.hdr, header, state.hdr_len);
 299
 300 #if 0
 301         printf("block_size:     %ld\n", block_size);
 302         printf("total_bytes:    %ld\n", total_bytes);
 303         printf("total_packets:  %ld\n", state.total_packets);
 304         printf("hdr_len:        %ld\n", state.hdr_len);
 305         printf("max_packet_len: %ld\n", max_packet_len);
 306 #endif
 307
 308         if (state.block_size > ETH_MAX_MTU - (
 309                 sizeof(struct iphdr) + sizeof(struct udphdr) +
 310                 state.hdr_len + max_packet_len)) {
 311                 printf("ALERT: slam blocksize to large\n");
 312                 return 0;
 313         }
 314         bitmap_len   = (state.total_packets + 1 + 7)/8;
 315         state.image  = phys_to_virt ( state.buffer->addr );
 316         /* We don't use the buffer routines properly yet; fake it */
 317         state.buffer->fill = total_bytes;
 318         state.bitmap = state.image + total_bytes;
 319         if ((unsigned long)state.image < 1024*1024) {
 320                 printf("ALERT: slam filesize to large for available memory\n");
 321                 return 0;
 322         }
 323         memset(state.bitmap, 0, bitmap_len);
 324
 325         return header + state.hdr_len;
 326 }
 327
 328 static int slam_recv_data(unsigned char *data)
 329 {
 330         unsigned long packet;
 331         unsigned long data_len;
 332         int err;
 333         struct udphdr *udp;
 334         udp = (struct udphdr *)&nic.packet[ETH_HLEN + sizeof(struct iphdr)];
 335         err = 0;
 336         packet = slam_decode(&data, &nic.packet[nic.packetlen], &err);
 337         if (err || (packet > state.total_packets)) {
 338                 printf("ALERT: Invalid packet number\n");
 339                 return 0;
 340         }
 341         /* Compute the expected data length */
 342         if (packet != state.total_packets -1) {
 343                 data_len = state.block_size;
 344         } else {
 345                 data_len = state.total_bytes % state.block_size;
 346         }
 347         /* If the packet size is wrong drop the packet and then continue */
 348         if (ntohs(udp->len) != (data_len + (data - (unsigned char*)udp))) {
 349                 printf("ALERT: udp packet is not the correct size\n");
 350                 return 1;
 351         }
 352         if (nic.packetlen < data_len + (data - nic.packet)) {
 353                 printf("ALERT: Ethernet packet shorter than data_len\n");
 354                 return 1;
 355         }
 356         if (data_len > state.block_size) {
 357                 data_len = state.block_size;
 358         }
 359         if (((state.bitmap[packet >> 3] >> (packet & 7)) & 1) == 0) {
 360                 /* Non duplicate packet */
 361                 state.bitmap[packet >> 3] |= (1 << (packet & 7));
 362                 memcpy(state.image + (packet*state.block_size), data, data_len);
 363                 state.received_packets++;
 364         } else {
 365 #ifdef MDEBUG
 366                 printf("<DUP>\n");
 367 #endif
 368         }
 369         return 1;
 370 }
 371
 372 static void transmit_nack(unsigned char *ptr, struct slam_info *info)
 373 {
 374         int nack_len;
 375         /* Ensure the packet is null terminated */
 376         *ptr++ = 0;
 377         nack_len = ptr - (unsigned char *)&nack;
 378         build_udp_hdr(info->server.sin_addr.s_addr, info->local.sin_port,
 379                       info->server.sin_port, 1, nack_len, &nack);
 380         ip_transmit(nack_len, &nack);
 381 #if defined(MDEBUG) && 0
 382         printf("Sent NACK to %@ bytes: %d have:%ld/%ld\n",
 383                 info->server_ip, nack_len,
 384                 state.received_packets, state.total_packets);
 385 #endif
 386 }
 387
 388 static void slam_send_nack(struct slam_info *info)
 389 {
 390         unsigned char *ptr, *end;
 391         /* Either I timed out or I was explicitly
 392          * asked for a request packet
 393          */
 394         ptr = &nack.data[0];
 395         /* Reserve space for the trailling null */
 396         end = &nack.data[sizeof(nack.data) -1];
 397         if (!state.bitmap) {
 398                 slam_encode(&ptr, end, 0);
 399                 slam_encode(&ptr, end, 1);
 400         }
 401         else {
 402                 /* Walk the bitmap */
 403                 unsigned long i;
 404                 unsigned long len;
 405                 unsigned long max;
 406                 int value;
 407                 int last;
 408                 /* Compute the last bit and store an inverted trailer */
 409                 max = state.total_packets;
 410                 value = ((state.bitmap[(max -1) >> 3] >> ((max -1) & 7) ) & 1);
 411                 value = !value;
 412                 state.bitmap[max >> 3] &= ~(1 << (max & 7));
 413                 state.bitmap[max >> 3] |= value << (max & 7);
 414
 415                 len = 0;
 416                 last = 1; /* Start with the received packets */
 417                 for(i = 0; i <= max; i++) {
 418                         value = (state.bitmap[i>>3] >> (i & 7)) & 1;
 419                         if (value == last) {
 420                                 len++;
 421                         } else {
 422                                 if (slam_encode(&ptr, end, len))
 423                                         break;
 424                                 last = value;
 425                                 len = 1;
 426                         }
 427                 }
 428         }
 429         info->sent_nack = 1;
 430         transmit_nack(ptr, info);
 431 }
 432
 433 static void slam_send_disconnect(struct slam_info *info)
 434 {
 435         if (info->sent_nack) {
 436                 /* A disconnect is a packet with just the null terminator */
 437                 transmit_nack(&nack.data[0], info);
 438         }
 439         info->sent_nack = 0;
 440 }
 441
 442
 443 static int proto_slam(struct slam_info *info)
 444 {
 445         int retry;
 446         long timeout;
 447
 448         init_slam_state();
 449         state.buffer = info->buffer;
 450
 451         retry = -1;
 452         rx_qdrain();
 453         /* Arp for my server */
 454         if (arptable[ARP_SERVER].ipaddr.s_addr != info->server.sin_addr.s_addr) {
 455                 arptable[ARP_SERVER].ipaddr.s_addr = info->server.sin_addr.s_addr;
 456                 memset(arptable[ARP_SERVER].node, 0, ETH_ALEN);
 457         }
 458         /* If I'm running over multicast join the multicast group */
 459         join_group(IGMP_SERVER, info->multicast.sin_addr.s_addr);
 460         for(;;) {
 461                 unsigned char *header;
 462                 unsigned char *data;
 463                 int type;
 464                 header = data = 0;
 465
 466                 timeout = slam_sleep_interval(retry);
 467                 type = await_reply(await_slam, 0, info, timeout);
 468                 /* Compute the timeout for next time */
 469                 if (type == SLAM_TIMEOUT) {
 470                         /* If I timeouted recompute the next timeout */
 471                         if (retry++ > SLAM_MAX_RETRIES) {
 472                                 return 0;
 473                         }
 474                 } else {
 475                         retry = 0;
 476                 }
 477                 if ((type == SLAM_DATA) || (type == SLAM_REQUEST)) {
 478                         /* Check the incomming packet and reinit the data
 479                          * structures if necessary.
 480                          */
 481                         header = &nic.packet[ETH_HLEN +
 482                                 sizeof(struct iphdr) + sizeof(struct udphdr)];
 483                         data = header + state.hdr_len;
 484                         if (memcmp(state.hdr, header, state.hdr_len) != 0) {
 485                                 /* Something is fishy reset the transaction */
 486                                 data = reinit_slam_state(header, &nic.packet[nic.packetlen]);
 487                                 if (!data) {
 488                                         return 0;
 489                                 }
 490                         }
 491                 }
 492                 if (type == SLAM_DATA) {
 493                         if (!slam_recv_data(data)) {
 494                                 return 0;
 495                         }
 496                         if (state.received_packets == state.total_packets) {
 497                                 /* We are done get out */
 498                                 break;
 499                         }
 500                 }
 501                 if ((type == SLAM_TIMEOUT) || (type == SLAM_REQUEST)) {
 502                         /* Either I timed out or I was explicitly
 503                          * asked by a request packet
 504                          */
 505                         slam_send_nack(info);
 506                 }
 507         }
 508         slam_send_disconnect(info);
 509
 510         /* Leave the multicast group */
 511         leave_group(IGMP_SERVER);
 512         /* FIXME don't overwrite myself */
 513         /* load file to correct location */
 514         return 1;
 515 }
 516
 517 static int url_slam ( char *url __unused, struct sockaddr_in *server,
 518                       char *file, struct buffer *buffer ) {
 519         struct slam_info info;
 520         /* Set the defaults */
 521         info.server = *server;
 522         info.multicast.sin_addr.s_addr = htonl(SLAM_MULTICAST_IP);
 523         info.multicast.sin_port      = SLAM_MULTICAST_PORT;
 524         info.local.sin_addr.s_addr   = arptable[ARP_CLIENT].ipaddr.s_addr;
 525         info.local.sin_port          = SLAM_LOCAL_PORT;
 526         info.buffer                  = buffer;
 527         info.sent_nack = 0;
 528         if (file[0]) {
 529                 printf("\nBad url\n");
 530                 return 0;
 531         }
 532         return proto_slam(&info);
 533 }
 534
 535 struct protocol slam_protocol __protocol = {
 536         .name = "x-slam",
 537         .default_port = SLAM_PORT,
 538         .load = url_slam,
 539 };
 540
 541 #endif