2 * Copyright (C) 2008 Michael Brown <mbrown@fensystems.co.uk>.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License as
6 * published by the Free Software Foundation; either version 2 of the
7 * License, or any later version.
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 FILE_LICENCE ( GPL2_OR_LATER );
28 #include <gpxe/features.h>
29 #include <gpxe/iobuf.h>
30 #include <gpxe/bitmap.h>
31 #include <gpxe/xfer.h>
32 #include <gpxe/open.h>
34 #include <gpxe/tcpip.h>
35 #include <gpxe/timer.h>
36 #include <gpxe/retry.h>
40 * Scalable Local Area Multicast protocol
42 * The SLAM protocol is supported only by Etherboot; it was designed
43 * and implemented by Eric Biederman. A server implementation is
44 * available in contrib/mini-slamd. There does not appear to be any
45 * documentation beyond a few sparse comments in Etherboot's
48 * SLAM packets use three types of data field:
50 * Nul : A single NUL (0) byte, used as a list terminator
52 * Raw : A block of raw data
54 * Int : A variable-length integer, in big-endian order. The length
55 * of the integer is encoded in the most significant three bits.
57 * Packets received by the client have the following layout:
59 * Int : Transaction identifier. This is an opaque value.
61 * Int : Total number of bytes in the transfer.
63 * Int : Block size, in bytes.
65 * Int : Packet sequence number within the transfer (if this packet
68 * Raw : Packet data (if this packet contains data).
70 * Packets transmitted by the client consist of a run-length-encoded
71 * representation of the received-blocks bitmap, looking something
74 * Int : Number of consecutive successfully-received packets
75 * Int : Number of consecutive missing packets
76 * Int : Number of consecutive successfully-received packets
77 * Int : Number of consecutive missing packets
83 FEATURE ( FEATURE_PROTOCOL, "SLAM", DHCP_EB_FEATURE_SLAM, 1 );
85 /** Default SLAM server port */
86 #define SLAM_DEFAULT_PORT 10000
88 /** Default SLAM multicast IP address */
89 #define SLAM_DEFAULT_MULTICAST_IP \
90 ( ( 239 << 24 ) | ( 255 << 16 ) | ( 1 << 8 ) | ( 1 << 0 ) )
92 /** Default SLAM multicast port */
93 #define SLAM_DEFAULT_MULTICAST_PORT 10000
95 /** Maximum SLAM header length */
96 #define SLAM_MAX_HEADER_LEN ( 7 /* transaction id */ + 7 /* total_bytes */ + \
99 /** Maximum number of blocks to request per NACK
101 * This is a policy decision equivalent to selecting a TCP window
104 #define SLAM_MAX_BLOCKS_PER_NACK 4
106 /** Maximum SLAM NACK length
108 * We only ever send a NACK for a single range of up to @c
109 * SLAM_MAX_BLOCKS_PER_NACK blocks.
111 #define SLAM_MAX_NACK_LEN ( 7 /* block */ + 7 /* #blocks */ + 1 /* NUL */ )
113 /** SLAM slave timeout */
114 #define SLAM_SLAVE_TIMEOUT ( 1 * TICKS_PER_SEC )
116 /** A SLAM request */
117 struct slam_request {
118 /** Reference counter */
119 struct refcnt refcnt;
121 /** Data transfer interface */
122 struct xfer_interface xfer;
123 /** Unicast socket */
124 struct xfer_interface socket;
125 /** Multicast socket */
126 struct xfer_interface mc_socket;
128 /** Master client retry timer */
129 struct retry_timer master_timer;
130 /** Slave client retry timer */
131 struct retry_timer slave_timer;
134 uint8_t header[SLAM_MAX_HEADER_LEN];
135 /** Size of cached header */
137 /** Total number of bytes in transfer */
138 unsigned long total_bytes;
139 /** Transfer block size */
140 unsigned long block_size;
141 /** Number of blocks in transfer */
142 unsigned long num_blocks;
144 struct bitmap bitmap;
145 /** NACK sent flag */
150 * Free a SLAM request
152 * @v refcnt Reference counter
154 static void slam_free ( struct refcnt *refcnt ) {
155 struct slam_request *slam =
156 container_of ( refcnt, struct slam_request, refcnt );
158 bitmap_free ( &slam->bitmap );
163 * Mark SLAM request as complete
165 * @v slam SLAM request
166 * @v rc Return status code
168 static void slam_finished ( struct slam_request *slam, int rc ) {
169 static const uint8_t slam_disconnect[] = { 0 };
171 DBGC ( slam, "SLAM %p finished with status code %d (%s)\n",
172 slam, rc, strerror ( rc ) );
174 /* Send a disconnect message if we ever sent anything to the
177 if ( slam->nack_sent ) {
178 xfer_deliver_raw ( &slam->socket, slam_disconnect,
179 sizeof ( slam_disconnect ) );
182 /* Stop the retry timers */
183 stop_timer ( &slam->master_timer );
184 stop_timer ( &slam->slave_timer );
186 /* Close all data transfer interfaces */
187 xfer_nullify ( &slam->socket );
188 xfer_close ( &slam->socket, rc );
189 xfer_nullify ( &slam->mc_socket );
190 xfer_close ( &slam->mc_socket, rc );
191 xfer_nullify ( &slam->xfer );
192 xfer_close ( &slam->xfer, rc );
195 /****************************************************************************
202 * Add a variable-length value to a SLAM packet
204 * @v slam SLAM request
205 * @v iobuf I/O buffer
206 * @v value Value to add
207 * @ret rc Return status code
209 * Adds a variable-length value to the end of an I/O buffer. Will
210 * always leave at least one byte of tailroom in the I/O buffer (to
211 * allow space for the terminating NUL).
213 static int slam_put_value ( struct slam_request *slam,
214 struct io_buffer *iobuf, unsigned long value ) {
219 /* Calculate variable length required to store value. Always
220 * leave at least one byte in the I/O buffer.
222 len = ( ( flsl ( value ) + 10 ) / 8 );
223 if ( len >= iob_tailroom ( iobuf ) ) {
224 DBGC2 ( slam, "SLAM %p cannot add %zd-byte value\n",
228 /* There is no valid way within the protocol that we can end
229 * up trying to push a full-sized long (i.e. without space for
230 * the length encoding).
232 assert ( len <= sizeof ( value ) );
235 data = iob_put ( iobuf, len );
236 for ( i = len ; i-- ; ) {
240 *data |= ( len << 5 );
241 assert ( value == 0 );
247 * Send SLAM NACK packet
249 * @v slam SLAM request
250 * @ret rc Return status code
252 static int slam_tx_nack ( struct slam_request *slam ) {
253 struct io_buffer *iobuf;
254 unsigned long first_block;
255 unsigned long num_blocks;
259 /* Mark NACK as sent, so that we know we have to disconnect later */
262 /* Allocate I/O buffer */
263 iobuf = xfer_alloc_iob ( &slam->socket, SLAM_MAX_NACK_LEN );
265 DBGC ( slam, "SLAM %p could not allocate I/O buffer\n",
270 /* Construct NACK. We always request only a single packet;
271 * this allows us to force multicast-TFTP-style flow control
272 * on the SLAM server, which will otherwise just blast the
273 * data out as fast as it can. On a gigabit network, without
274 * RX checksumming, this would inevitably cause packet drops.
276 first_block = bitmap_first_gap ( &slam->bitmap );
277 for ( num_blocks = 1 ; ; num_blocks++ ) {
278 if ( num_blocks >= SLAM_MAX_BLOCKS_PER_NACK )
280 if ( ( first_block + num_blocks ) >= slam->num_blocks )
282 if ( bitmap_test ( &slam->bitmap,
283 ( first_block + num_blocks ) ) )
287 DBGCP ( slam, "SLAM %p transmitting NACK for blocks "
288 "%ld-%ld\n", slam, first_block,
289 ( first_block + num_blocks - 1 ) );
291 DBGC ( slam, "SLAM %p transmitting initial NACK for blocks "
292 "0-%ld\n", slam, ( num_blocks - 1 ) );
294 if ( ( rc = slam_put_value ( slam, iobuf, first_block ) ) != 0 )
296 if ( ( rc = slam_put_value ( slam, iobuf, num_blocks ) ) != 0 )
298 nul = iob_put ( iobuf, 1 );
301 /* Transmit packet */
302 return xfer_deliver_iob ( &slam->socket, iobuf );
306 * Handle SLAM master client retry timer expiry
308 * @v timer Master retry timer
309 * @v fail Failure indicator
311 static void slam_master_timer_expired ( struct retry_timer *timer,
313 struct slam_request *slam =
314 container_of ( timer, struct slam_request, master_timer );
317 /* Allow timer to stop running. We will terminate the
318 * connection only if the slave timer times out.
320 DBGC ( slam, "SLAM %p giving up acting as master client\n",
323 /* Retransmit NACK */
324 start_timer ( timer );
325 slam_tx_nack ( slam );
330 * Handle SLAM slave client retry timer expiry
332 * @v timer Master retry timer
333 * @v fail Failure indicator
335 static void slam_slave_timer_expired ( struct retry_timer *timer,
337 struct slam_request *slam =
338 container_of ( timer, struct slam_request, slave_timer );
341 /* Terminate connection */
342 slam_finished ( slam, -ETIMEDOUT );
344 /* Try sending a NACK */
345 DBGC ( slam, "SLAM %p trying to become master client\n",
347 start_timer ( timer );
348 slam_tx_nack ( slam );
352 /****************************************************************************
359 * Read and strip a variable-length value from a SLAM packet
361 * @v slam SLAM request
362 * @v iobuf I/O buffer
363 * @v value Value to fill in, or NULL to ignore value
364 * @ret rc Return status code
366 * Reads a variable-length value from the start of the I/O buffer.
368 static int slam_pull_value ( struct slam_request *slam,
369 struct io_buffer *iobuf,
370 unsigned long *value ) {
375 if ( iob_len ( iobuf ) == 0 ) {
376 DBGC ( slam, "SLAM %p empty value\n", slam );
380 /* Read and verify length of value */
382 len = ( *data >> 5 );
384 ( value && ( len > sizeof ( *value ) ) ) ) {
385 DBGC ( slam, "SLAM %p invalid value length %zd bytes\n",
389 if ( len > iob_len ( iobuf ) ) {
390 DBGC ( slam, "SLAM %p value extends beyond I/O buffer\n",
396 iob_pull ( iobuf, len );
397 *value = ( *data & 0x1f );
407 * Read and strip SLAM header
409 * @v slam SLAM request
410 * @v iobuf I/O buffer
411 * @ret rc Return status code
413 static int slam_pull_header ( struct slam_request *slam,
414 struct io_buffer *iobuf ) {
415 void *header = iobuf->data;
418 /* If header matches cached header, just pull it and return */
419 if ( ( slam->header_len <= iob_len ( iobuf ) ) &&
420 ( memcmp ( slam->header, iobuf->data, slam->header_len ) == 0 )){
421 iob_pull ( iobuf, slam->header_len );
425 DBGC ( slam, "SLAM %p detected changed header; resetting\n", slam );
427 /* Read and strip transaction ID, total number of bytes, and
430 if ( ( rc = slam_pull_value ( slam, iobuf, NULL ) ) != 0 )
432 if ( ( rc = slam_pull_value ( slam, iobuf,
433 &slam->total_bytes ) ) != 0 )
435 if ( ( rc = slam_pull_value ( slam, iobuf,
436 &slam->block_size ) ) != 0 )
439 /* Update the cached header */
440 slam->header_len = ( iobuf->data - header );
441 assert ( slam->header_len <= sizeof ( slam->header ) );
442 memcpy ( slam->header, header, slam->header_len );
444 /* Calculate number of blocks */
445 slam->num_blocks = ( ( slam->total_bytes + slam->block_size - 1 ) /
448 DBGC ( slam, "SLAM %p has total bytes %ld, block size %ld, num "
449 "blocks %ld\n", slam, slam->total_bytes, slam->block_size,
452 /* Discard and reset the bitmap */
453 bitmap_free ( &slam->bitmap );
454 memset ( &slam->bitmap, 0, sizeof ( slam->bitmap ) );
456 /* Allocate a new bitmap */
457 if ( ( rc = bitmap_resize ( &slam->bitmap,
458 slam->num_blocks ) ) != 0 ) {
459 /* Failure to allocate a bitmap is fatal */
460 DBGC ( slam, "SLAM %p could not allocate bitmap for %ld "
461 "blocks: %s\n", slam, slam->num_blocks,
463 slam_finished ( slam, rc );
467 /* Notify recipient of file size */
468 xfer_seek ( &slam->xfer, slam->total_bytes, SEEK_SET );
474 * Receive SLAM data packet
476 * @v mc_socket SLAM multicast socket
477 * @v iobuf I/O buffer
478 * @ret rc Return status code
480 static int slam_mc_socket_deliver ( struct xfer_interface *mc_socket,
481 struct io_buffer *iobuf,
482 struct xfer_metadata *rx_meta __unused ) {
483 struct slam_request *slam =
484 container_of ( mc_socket, struct slam_request, mc_socket );
485 struct xfer_metadata meta;
486 unsigned long packet;
490 /* Stop the master client timer. Restart the slave client timer. */
491 stop_timer ( &slam->master_timer );
492 stop_timer ( &slam->slave_timer );
493 start_timer_fixed ( &slam->slave_timer, SLAM_SLAVE_TIMEOUT );
495 /* Read and strip packet header */
496 if ( ( rc = slam_pull_header ( slam, iobuf ) ) != 0 )
499 /* Read and strip packet number */
500 if ( ( rc = slam_pull_value ( slam, iobuf, &packet ) ) != 0 )
503 /* Sanity check packet number */
504 if ( packet >= slam->num_blocks ) {
505 DBGC ( slam, "SLAM %p received out-of-range packet %ld "
506 "(num_blocks=%ld)\n", slam, packet, slam->num_blocks );
511 /* Sanity check length */
512 len = iob_len ( iobuf );
513 if ( len > slam->block_size ) {
514 DBGC ( slam, "SLAM %p received oversize packet of %zd bytes "
515 "(block_size=%ld)\n", slam, len, slam->block_size );
519 if ( ( packet != ( slam->num_blocks - 1 ) ) &&
520 ( len < slam->block_size ) ) {
521 DBGC ( slam, "SLAM %p received short packet of %zd bytes "
522 "(block_size=%ld)\n", slam, len, slam->block_size );
527 /* If we have already seen this packet, discard it */
528 if ( bitmap_test ( &slam->bitmap, packet ) ) {
532 /* Pass to recipient */
533 memset ( &meta, 0, sizeof ( meta ) );
534 meta.whence = SEEK_SET;
535 meta.offset = ( packet * slam->block_size );
536 if ( ( rc = xfer_deliver_iob_meta ( &slam->xfer, iobuf,
540 /* Mark block as received */
541 bitmap_set ( &slam->bitmap, packet );
543 /* If we have received all blocks, terminate */
544 if ( bitmap_full ( &slam->bitmap ) )
545 slam_finished ( slam, 0 );
557 * Receive SLAM non-data packet
559 * @v socket SLAM unicast socket
560 * @v iobuf I/O buffer
561 * @ret rc Return status code
563 static int slam_socket_deliver ( struct xfer_interface *socket,
564 struct io_buffer *iobuf,
565 struct xfer_metadata *rx_meta __unused ) {
566 struct slam_request *slam =
567 container_of ( socket, struct slam_request, socket );
570 /* Restart the master client timer */
571 stop_timer ( &slam->master_timer );
572 start_timer ( &slam->master_timer );
574 /* Read and strip packet header */
575 if ( ( rc = slam_pull_header ( slam, iobuf ) ) != 0 )
579 if ( iob_len ( iobuf ) != 0 ) {
580 DBGC ( slam, "SLAM %p received trailing garbage:\n", slam );
581 DBGC_HD ( slam, iobuf->data, iob_len ( iobuf ) );
589 /* Send NACK in reply */
590 slam_tx_nack ( slam );
601 * Close SLAM unicast socket
603 * @v socket SLAM unicast socket
604 * @v rc Reason for close
606 static void slam_socket_close ( struct xfer_interface *socket, int rc ) {
607 struct slam_request *slam =
608 container_of ( socket, struct slam_request, socket );
610 DBGC ( slam, "SLAM %p unicast socket closed: %s\n",
611 slam, strerror ( rc ) );
613 slam_finished ( slam, rc );
616 /** SLAM unicast socket data transfer operations */
617 static struct xfer_interface_operations slam_socket_operations = {
618 .close = slam_socket_close,
619 .vredirect = xfer_vreopen,
620 .window = unlimited_xfer_window,
621 .alloc_iob = default_xfer_alloc_iob,
622 .deliver_iob = slam_socket_deliver,
623 .deliver_raw = xfer_deliver_as_iob,
627 * Close SLAM multicast socket
629 * @v mc_socket SLAM multicast socket
630 * @v rc Reason for close
632 static void slam_mc_socket_close ( struct xfer_interface *mc_socket, int rc ){
633 struct slam_request *slam =
634 container_of ( mc_socket, struct slam_request, mc_socket );
636 DBGC ( slam, "SLAM %p multicast socket closed: %s\n",
637 slam, strerror ( rc ) );
639 slam_finished ( slam, rc );
642 /** SLAM multicast socket data transfer operations */
643 static struct xfer_interface_operations slam_mc_socket_operations = {
644 .close = slam_mc_socket_close,
645 .vredirect = xfer_vreopen,
646 .window = unlimited_xfer_window,
647 .alloc_iob = default_xfer_alloc_iob,
648 .deliver_iob = slam_mc_socket_deliver,
649 .deliver_raw = xfer_deliver_as_iob,
652 /****************************************************************************
654 * Data transfer interface
659 * Close SLAM data transfer interface
661 * @v xfer SLAM data transfer interface
662 * @v rc Reason for close
664 static void slam_xfer_close ( struct xfer_interface *xfer, int rc ) {
665 struct slam_request *slam =
666 container_of ( xfer, struct slam_request, xfer );
668 DBGC ( slam, "SLAM %p data transfer interface closed: %s\n",
669 slam, strerror ( rc ) );
671 slam_finished ( slam, rc );
674 /** SLAM data transfer operations */
675 static struct xfer_interface_operations slam_xfer_operations = {
676 .close = slam_xfer_close,
677 .vredirect = ignore_xfer_vredirect,
678 .window = unlimited_xfer_window,
679 .alloc_iob = default_xfer_alloc_iob,
680 .deliver_iob = xfer_deliver_as_raw,
681 .deliver_raw = ignore_xfer_deliver_raw,
685 * Parse SLAM URI multicast address
687 * @v slam SLAM request
688 * @v path Path portion of x-slam:// URI
689 * @v address Socket address to fill in
690 * @ret rc Return status code
692 static int slam_parse_multicast_address ( struct slam_request *slam,
694 struct sockaddr_in *address ) {
695 char path_dup[ strlen ( path ) /* no +1 */ ];
699 /* Create temporary copy of path, minus the leading '/' */
700 assert ( *path == '/' );
701 memcpy ( path_dup, ( path + 1 ) , sizeof ( path_dup ) );
703 /* Parse port, if present */
704 sep = strchr ( path_dup, ':' );
707 address->sin_port = htons ( strtoul ( sep, &end, 0 ) );
708 if ( *end != '\0' ) {
709 DBGC ( slam, "SLAM %p invalid multicast port "
710 "\"%s\"\n", slam, sep );
716 if ( inet_aton ( path_dup, &address->sin_addr ) == 0 ) {
717 DBGC ( slam, "SLAM %p invalid multicast address \"%s\"\n",
726 * Initiate a SLAM request
728 * @v xfer Data transfer interface
729 * @v uri Uniform Resource Identifier
730 * @ret rc Return status code
732 static int slam_open ( struct xfer_interface *xfer, struct uri *uri ) {
733 static const struct sockaddr_in default_multicast = {
734 .sin_family = AF_INET,
735 .sin_port = htons ( SLAM_DEFAULT_MULTICAST_PORT ),
736 .sin_addr = { htonl ( SLAM_DEFAULT_MULTICAST_IP ) },
738 struct slam_request *slam;
739 struct sockaddr_tcpip server;
740 struct sockaddr_in multicast;
747 /* Allocate and populate structure */
748 slam = zalloc ( sizeof ( *slam ) );
751 slam->refcnt.free = slam_free;
752 xfer_init ( &slam->xfer, &slam_xfer_operations, &slam->refcnt );
753 xfer_init ( &slam->socket, &slam_socket_operations, &slam->refcnt );
754 xfer_init ( &slam->mc_socket, &slam_mc_socket_operations,
756 slam->master_timer.expired = slam_master_timer_expired;
757 slam->slave_timer.expired = slam_slave_timer_expired;
758 /* Fake an invalid cached header of { 0x00, ... } */
759 slam->header_len = 1;
760 /* Fake parameters for initial NACK */
761 slam->num_blocks = 1;
762 if ( ( rc = bitmap_resize ( &slam->bitmap, 1 ) ) != 0 ) {
763 DBGC ( slam, "SLAM %p could not allocate initial bitmap: "
764 "%s\n", slam, strerror ( rc ) );
768 /* Open unicast socket */
769 memset ( &server, 0, sizeof ( server ) );
770 server.st_port = htons ( uri_port ( uri, SLAM_DEFAULT_PORT ) );
771 if ( ( rc = xfer_open_named_socket ( &slam->socket, SOCK_DGRAM,
772 ( struct sockaddr * ) &server,
773 uri->host, NULL ) ) != 0 ) {
774 DBGC ( slam, "SLAM %p could not open unicast socket: %s\n",
775 slam, strerror ( rc ) );
779 /* Open multicast socket */
780 memcpy ( &multicast, &default_multicast, sizeof ( multicast ) );
782 ( ( rc = slam_parse_multicast_address ( slam, uri->path,
783 &multicast ) ) != 0 ) ) {
786 if ( ( rc = xfer_open_socket ( &slam->mc_socket, SOCK_DGRAM,
787 ( struct sockaddr * ) &multicast,
788 ( struct sockaddr * ) &multicast ) ) != 0 ) {
789 DBGC ( slam, "SLAM %p could not open multicast socket: %s\n",
790 slam, strerror ( rc ) );
794 /* Start slave retry timer */
795 start_timer_fixed ( &slam->slave_timer, SLAM_SLAVE_TIMEOUT );
797 /* Attach to parent interface, mortalise self, and return */
798 xfer_plug_plug ( &slam->xfer, xfer );
799 ref_put ( &slam->refcnt );
803 slam_finished ( slam, rc );
804 ref_put ( &slam->refcnt );
808 /** SLAM URI opener */
809 struct uri_opener slam_uri_opener __uri_opener = {