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., 51 Franklin Street, Fifth Floor, Boston, MA
19 * You can also choose to distribute this program under the terms of
20 * the Unmodified Binary Distribution Licence (as given in the file
21 * COPYING.UBDL), provided that you have satisfied its requirements.
24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
33 #include <ipxe/features.h>
34 #include <ipxe/iobuf.h>
35 #include <ipxe/bitmap.h>
36 #include <ipxe/xfer.h>
37 #include <ipxe/open.h>
39 #include <ipxe/tcpip.h>
40 #include <ipxe/timer.h>
41 #include <ipxe/retry.h>
45 * Scalable Local Area Multicast protocol
47 * The SLAM protocol is supported only by Etherboot; it was designed
48 * and implemented by Eric Biederman. A server implementation is
49 * available in contrib/mini-slamd. There does not appear to be any
50 * documentation beyond a few sparse comments in Etherboot's
53 * SLAM packets use three types of data field:
55 * Nul : A single NUL (0) byte, used as a list terminator
57 * Raw : A block of raw data
59 * Int : A variable-length integer, in big-endian order. The length
60 * of the integer is encoded in the most significant three bits.
62 * Packets received by the client have the following layout:
64 * Int : Transaction identifier. This is an opaque value.
66 * Int : Total number of bytes in the transfer.
68 * Int : Block size, in bytes.
70 * Int : Packet sequence number within the transfer (if this packet
73 * Raw : Packet data (if this packet contains data).
75 * Packets transmitted by the client consist of a run-length-encoded
76 * representation of the received-blocks bitmap, looking something
79 * Int : Number of consecutive successfully-received packets
80 * Int : Number of consecutive missing packets
81 * Int : Number of consecutive successfully-received packets
82 * Int : Number of consecutive missing packets
88 FEATURE ( FEATURE_PROTOCOL, "SLAM", DHCP_EB_FEATURE_SLAM, 1 );
90 /** Default SLAM server port */
91 #define SLAM_DEFAULT_PORT 10000
93 /** Default SLAM multicast IP address */
94 #define SLAM_DEFAULT_MULTICAST_IP \
95 ( ( 239 << 24 ) | ( 255 << 16 ) | ( 1 << 8 ) | ( 1 << 0 ) )
97 /** Default SLAM multicast port */
98 #define SLAM_DEFAULT_MULTICAST_PORT 10000
100 /** Maximum SLAM header length */
101 #define SLAM_MAX_HEADER_LEN ( 7 /* transaction id */ + 7 /* total_bytes */ + \
104 /** Maximum number of blocks to request per NACK
106 * This is a policy decision equivalent to selecting a TCP window
109 #define SLAM_MAX_BLOCKS_PER_NACK 4
111 /** Maximum SLAM NACK length
113 * We only ever send a NACK for a single range of up to @c
114 * SLAM_MAX_BLOCKS_PER_NACK blocks.
116 #define SLAM_MAX_NACK_LEN ( 7 /* block */ + 7 /* #blocks */ + 1 /* NUL */ )
118 /** SLAM slave timeout */
119 #define SLAM_SLAVE_TIMEOUT ( 1 * TICKS_PER_SEC )
121 /** A SLAM request */
122 struct slam_request {
123 /** Reference counter */
124 struct refcnt refcnt;
126 /** Data transfer interface */
127 struct interface xfer;
128 /** Unicast socket */
129 struct interface socket;
130 /** Multicast socket */
131 struct interface mc_socket;
133 /** Master client retry timer */
134 struct retry_timer master_timer;
135 /** Slave client retry timer */
136 struct retry_timer slave_timer;
139 uint8_t header[SLAM_MAX_HEADER_LEN];
140 /** Size of cached header */
142 /** Total number of bytes in transfer */
143 unsigned long total_bytes;
144 /** Transfer block size */
145 unsigned long block_size;
146 /** Number of blocks in transfer */
147 unsigned long num_blocks;
149 struct bitmap bitmap;
150 /** NACK sent flag */
155 * Free a SLAM request
157 * @v refcnt Reference counter
159 static void slam_free ( struct refcnt *refcnt ) {
160 struct slam_request *slam =
161 container_of ( refcnt, struct slam_request, refcnt );
163 bitmap_free ( &slam->bitmap );
168 * Mark SLAM request as complete
170 * @v slam SLAM request
171 * @v rc Return status code
173 static void slam_finished ( struct slam_request *slam, int rc ) {
174 static const uint8_t slam_disconnect[] = { 0 };
176 DBGC ( slam, "SLAM %p finished with status code %d (%s)\n",
177 slam, rc, strerror ( rc ) );
179 /* Send a disconnect message if we ever sent anything to the
182 if ( slam->nack_sent ) {
183 xfer_deliver_raw ( &slam->socket, slam_disconnect,
184 sizeof ( slam_disconnect ) );
187 /* Stop the retry timers */
188 stop_timer ( &slam->master_timer );
189 stop_timer ( &slam->slave_timer );
191 /* Close all data transfer interfaces */
192 intf_shutdown ( &slam->socket, rc );
193 intf_shutdown ( &slam->mc_socket, rc );
194 intf_shutdown ( &slam->xfer, rc );
197 /****************************************************************************
204 * Add a variable-length value to a SLAM packet
206 * @v slam SLAM request
207 * @v iobuf I/O buffer
208 * @v value Value to add
209 * @ret rc Return status code
211 * Adds a variable-length value to the end of an I/O buffer. Will
212 * always leave at least one byte of tailroom in the I/O buffer (to
213 * allow space for the terminating NUL).
215 static int slam_put_value ( struct slam_request *slam,
216 struct io_buffer *iobuf, unsigned long value ) {
221 /* Calculate variable length required to store value. Always
222 * leave at least one byte in the I/O buffer.
224 len = ( ( flsl ( value ) + 10 ) / 8 );
225 if ( len >= iob_tailroom ( iobuf ) ) {
226 DBGC2 ( slam, "SLAM %p cannot add %zd-byte value\n",
230 /* There is no valid way within the protocol that we can end
231 * up trying to push a full-sized long (i.e. without space for
232 * the length encoding).
234 assert ( len <= sizeof ( value ) );
237 data = iob_put ( iobuf, len );
238 for ( i = len ; i-- ; ) {
242 *data |= ( len << 5 );
243 assert ( value == 0 );
249 * Send SLAM NACK packet
251 * @v slam SLAM request
252 * @ret rc Return status code
254 static int slam_tx_nack ( struct slam_request *slam ) {
255 struct io_buffer *iobuf;
256 unsigned long first_block;
257 unsigned long num_blocks;
261 /* Mark NACK as sent, so that we know we have to disconnect later */
264 /* Allocate I/O buffer */
265 iobuf = xfer_alloc_iob ( &slam->socket, SLAM_MAX_NACK_LEN );
267 DBGC ( slam, "SLAM %p could not allocate I/O buffer\n",
272 /* Construct NACK. We always request only a single packet;
273 * this allows us to force multicast-TFTP-style flow control
274 * on the SLAM server, which will otherwise just blast the
275 * data out as fast as it can. On a gigabit network, without
276 * RX checksumming, this would inevitably cause packet drops.
278 first_block = bitmap_first_gap ( &slam->bitmap );
279 for ( num_blocks = 1 ; ; num_blocks++ ) {
280 if ( num_blocks >= SLAM_MAX_BLOCKS_PER_NACK )
282 if ( ( first_block + num_blocks ) >= slam->num_blocks )
284 if ( bitmap_test ( &slam->bitmap,
285 ( first_block + num_blocks ) ) )
289 DBGCP ( slam, "SLAM %p transmitting NACK for blocks "
290 "%ld-%ld\n", slam, first_block,
291 ( first_block + num_blocks - 1 ) );
293 DBGC ( slam, "SLAM %p transmitting initial NACK for blocks "
294 "0-%ld\n", slam, ( num_blocks - 1 ) );
296 if ( ( rc = slam_put_value ( slam, iobuf, first_block ) ) != 0 )
298 if ( ( rc = slam_put_value ( slam, iobuf, num_blocks ) ) != 0 )
300 nul = iob_put ( iobuf, 1 );
303 /* Transmit packet */
304 return xfer_deliver_iob ( &slam->socket, iobuf );
308 * Handle SLAM master client retry timer expiry
310 * @v timer Master retry timer
311 * @v fail Failure indicator
313 static void slam_master_timer_expired ( struct retry_timer *timer,
315 struct slam_request *slam =
316 container_of ( timer, struct slam_request, master_timer );
319 /* Allow timer to stop running. We will terminate the
320 * connection only if the slave timer times out.
322 DBGC ( slam, "SLAM %p giving up acting as master client\n",
325 /* Retransmit NACK */
326 start_timer ( timer );
327 slam_tx_nack ( slam );
332 * Handle SLAM slave client retry timer expiry
334 * @v timer Master retry timer
335 * @v fail Failure indicator
337 static void slam_slave_timer_expired ( struct retry_timer *timer,
339 struct slam_request *slam =
340 container_of ( timer, struct slam_request, slave_timer );
343 /* Terminate connection */
344 slam_finished ( slam, -ETIMEDOUT );
346 /* Try sending a NACK */
347 DBGC ( slam, "SLAM %p trying to become master client\n",
349 start_timer ( timer );
350 slam_tx_nack ( slam );
354 /****************************************************************************
361 * Read and strip a variable-length value from a SLAM packet
363 * @v slam SLAM request
364 * @v iobuf I/O buffer
365 * @v value Value to fill in, or NULL to ignore value
366 * @ret rc Return status code
368 * Reads a variable-length value from the start of the I/O buffer.
370 static int slam_pull_value ( struct slam_request *slam,
371 struct io_buffer *iobuf,
372 unsigned long *value ) {
377 if ( iob_len ( iobuf ) == 0 ) {
378 DBGC ( slam, "SLAM %p empty value\n", slam );
382 /* Read and verify length of value */
384 len = ( *data >> 5 );
386 ( value && ( len > sizeof ( *value ) ) ) ) {
387 DBGC ( slam, "SLAM %p invalid value length %zd bytes\n",
391 if ( len > iob_len ( iobuf ) ) {
392 DBGC ( slam, "SLAM %p value extends beyond I/O buffer\n",
398 iob_pull ( iobuf, len );
399 *value = ( *data & 0x1f );
409 * Read and strip SLAM header
411 * @v slam SLAM request
412 * @v iobuf I/O buffer
413 * @ret rc Return status code
415 static int slam_pull_header ( struct slam_request *slam,
416 struct io_buffer *iobuf ) {
417 void *header = iobuf->data;
420 /* If header matches cached header, just pull it and return */
421 if ( ( slam->header_len <= iob_len ( iobuf ) ) &&
422 ( memcmp ( slam->header, iobuf->data, slam->header_len ) == 0 )){
423 iob_pull ( iobuf, slam->header_len );
427 DBGC ( slam, "SLAM %p detected changed header; resetting\n", slam );
429 /* Read and strip transaction ID, total number of bytes, and
432 if ( ( rc = slam_pull_value ( slam, iobuf, NULL ) ) != 0 )
434 if ( ( rc = slam_pull_value ( slam, iobuf,
435 &slam->total_bytes ) ) != 0 )
437 if ( ( rc = slam_pull_value ( slam, iobuf,
438 &slam->block_size ) ) != 0 )
441 /* Update the cached header */
442 slam->header_len = ( iobuf->data - header );
443 assert ( slam->header_len <= sizeof ( slam->header ) );
444 memcpy ( slam->header, header, slam->header_len );
446 /* Calculate number of blocks */
447 slam->num_blocks = ( ( slam->total_bytes + slam->block_size - 1 ) /
450 DBGC ( slam, "SLAM %p has total bytes %ld, block size %ld, num "
451 "blocks %ld\n", slam, slam->total_bytes, slam->block_size,
454 /* Discard and reset the bitmap */
455 bitmap_free ( &slam->bitmap );
456 memset ( &slam->bitmap, 0, sizeof ( slam->bitmap ) );
458 /* Allocate a new bitmap */
459 if ( ( rc = bitmap_resize ( &slam->bitmap,
460 slam->num_blocks ) ) != 0 ) {
461 /* Failure to allocate a bitmap is fatal */
462 DBGC ( slam, "SLAM %p could not allocate bitmap for %ld "
463 "blocks: %s\n", slam, slam->num_blocks,
465 slam_finished ( slam, rc );
469 /* Notify recipient of file size */
470 xfer_seek ( &slam->xfer, slam->total_bytes );
476 * Receive SLAM data packet
478 * @v slam SLAM request
479 * @v iobuf I/O buffer
480 * @ret rc Return status code
482 static int slam_mc_socket_deliver ( struct slam_request *slam,
483 struct io_buffer *iobuf,
484 struct xfer_metadata *rx_meta __unused ) {
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.flags = XFER_FL_ABS_OFFSET;
535 meta.offset = ( packet * slam->block_size );
536 if ( ( rc = xfer_deliver ( &slam->xfer, iobuf, &meta ) ) != 0 )
539 /* Mark block as received */
540 bitmap_set ( &slam->bitmap, packet );
542 /* If we have received all blocks, terminate */
543 if ( bitmap_full ( &slam->bitmap ) )
544 slam_finished ( slam, 0 );
556 * Receive SLAM non-data packet
558 * @v slam SLAM request
559 * @v iobuf I/O buffer
560 * @ret rc Return status code
562 static int slam_socket_deliver ( struct slam_request *slam,
563 struct io_buffer *iobuf,
564 struct xfer_metadata *rx_meta __unused ) {
567 /* Restart the master client timer */
568 stop_timer ( &slam->master_timer );
569 start_timer ( &slam->master_timer );
571 /* Read and strip packet header */
572 if ( ( rc = slam_pull_header ( slam, iobuf ) ) != 0 )
576 if ( iob_len ( iobuf ) != 0 ) {
577 DBGC ( slam, "SLAM %p received trailing garbage:\n", slam );
578 DBGC_HD ( slam, iobuf->data, iob_len ( iobuf ) );
586 /* Send NACK in reply */
587 slam_tx_nack ( slam );
597 /** SLAM unicast socket interface operations */
598 static struct interface_operation slam_socket_operations[] = {
599 INTF_OP ( xfer_deliver, struct slam_request *, slam_socket_deliver ),
600 INTF_OP ( intf_close, struct slam_request *, slam_finished ),
603 /** SLAM unicast socket interface descriptor */
604 static struct interface_descriptor slam_socket_desc =
605 INTF_DESC ( struct slam_request, socket, slam_socket_operations );
607 /** SLAM multicast socket interface operations */
608 static struct interface_operation slam_mc_socket_operations[] = {
609 INTF_OP ( xfer_deliver, struct slam_request *, slam_mc_socket_deliver ),
610 INTF_OP ( intf_close, struct slam_request *, slam_finished ),
613 /** SLAM multicast socket interface descriptor */
614 static struct interface_descriptor slam_mc_socket_desc =
615 INTF_DESC ( struct slam_request, mc_socket, slam_mc_socket_operations );
617 /****************************************************************************
619 * Data transfer interface
623 /** SLAM data transfer interface operations */
624 static struct interface_operation slam_xfer_operations[] = {
625 INTF_OP ( intf_close, struct slam_request *, slam_finished ),
628 /** SLAM data transfer interface descriptor */
629 static struct interface_descriptor slam_xfer_desc =
630 INTF_DESC ( struct slam_request, xfer, slam_xfer_operations );
633 * Parse SLAM URI multicast address
635 * @v slam SLAM request
636 * @v path Path portion of x-slam:// URI
637 * @v address Socket address to fill in
638 * @ret rc Return status code
640 static int slam_parse_multicast_address ( struct slam_request *slam,
642 struct sockaddr_in *address ) {
643 char path_dup[ strlen ( path ) /* no +1 */ ];
647 /* Create temporary copy of path, minus the leading '/' */
648 assert ( *path == '/' );
649 memcpy ( path_dup, ( path + 1 ) , sizeof ( path_dup ) );
651 /* Parse port, if present */
652 sep = strchr ( path_dup, ':' );
655 address->sin_port = htons ( strtoul ( sep, &end, 0 ) );
656 if ( *end != '\0' ) {
657 DBGC ( slam, "SLAM %p invalid multicast port "
658 "\"%s\"\n", slam, sep );
664 if ( inet_aton ( path_dup, &address->sin_addr ) == 0 ) {
665 DBGC ( slam, "SLAM %p invalid multicast address \"%s\"\n",
674 * Initiate a SLAM request
676 * @v xfer Data transfer interface
677 * @v uri Uniform Resource Identifier
678 * @ret rc Return status code
680 static int slam_open ( struct interface *xfer, struct uri *uri ) {
681 static const struct sockaddr_in default_multicast = {
682 .sin_family = AF_INET,
683 .sin_port = htons ( SLAM_DEFAULT_MULTICAST_PORT ),
684 .sin_addr = { htonl ( SLAM_DEFAULT_MULTICAST_IP ) },
686 struct slam_request *slam;
687 struct sockaddr_tcpip server;
688 struct sockaddr_in multicast;
695 /* Allocate and populate structure */
696 slam = zalloc ( sizeof ( *slam ) );
699 ref_init ( &slam->refcnt, slam_free );
700 intf_init ( &slam->xfer, &slam_xfer_desc, &slam->refcnt );
701 intf_init ( &slam->socket, &slam_socket_desc, &slam->refcnt );
702 intf_init ( &slam->mc_socket, &slam_mc_socket_desc, &slam->refcnt );
703 timer_init ( &slam->master_timer, slam_master_timer_expired,
705 timer_init ( &slam->slave_timer, slam_slave_timer_expired,
707 /* Fake an invalid cached header of { 0x00, ... } */
708 slam->header_len = 1;
709 /* Fake parameters for initial NACK */
710 slam->num_blocks = 1;
711 if ( ( rc = bitmap_resize ( &slam->bitmap, 1 ) ) != 0 ) {
712 DBGC ( slam, "SLAM %p could not allocate initial bitmap: "
713 "%s\n", slam, strerror ( rc ) );
717 /* Open unicast socket */
718 memset ( &server, 0, sizeof ( server ) );
719 server.st_port = htons ( uri_port ( uri, SLAM_DEFAULT_PORT ) );
720 if ( ( rc = xfer_open_named_socket ( &slam->socket, SOCK_DGRAM,
721 ( struct sockaddr * ) &server,
722 uri->host, NULL ) ) != 0 ) {
723 DBGC ( slam, "SLAM %p could not open unicast socket: %s\n",
724 slam, strerror ( rc ) );
728 /* Open multicast socket */
729 memcpy ( &multicast, &default_multicast, sizeof ( multicast ) );
731 ( ( rc = slam_parse_multicast_address ( slam, uri->path,
732 &multicast ) ) != 0 ) ) {
735 if ( ( rc = xfer_open_socket ( &slam->mc_socket, SOCK_DGRAM,
736 ( struct sockaddr * ) &multicast,
737 ( struct sockaddr * ) &multicast ) ) != 0 ) {
738 DBGC ( slam, "SLAM %p could not open multicast socket: %s\n",
739 slam, strerror ( rc ) );
743 /* Start slave retry timer */
744 start_timer_fixed ( &slam->slave_timer, SLAM_SLAVE_TIMEOUT );
746 /* Attach to parent interface, mortalise self, and return */
747 intf_plug_plug ( &slam->xfer, xfer );
748 ref_put ( &slam->refcnt );
752 slam_finished ( slam, rc );
753 ref_put ( &slam->refcnt );
757 /** SLAM URI opener */
758 struct uri_opener slam_uri_opener __uri_opener = {