a25c30de8589a68a8cc1ed511576a0c42789abf7
[people/balajirrao/gpxe.git] / 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