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
20 FILE_LICENCE ( GPL2_OR_LATER );
29 #include <ipxe/features.h>
30 #include <ipxe/iobuf.h>
31 #include <ipxe/bitmap.h>
32 #include <ipxe/xfer.h>
33 #include <ipxe/open.h>
35 #include <ipxe/tcpip.h>
36 #include <ipxe/timer.h>
37 #include <ipxe/retry.h>
41 * Scalable Local Area Multicast protocol
43 * The SLAM protocol is supported only by Etherboot; it was designed
44 * and implemented by Eric Biederman. A server implementation is
45 * available in contrib/mini-slamd. There does not appear to be any
46 * documentation beyond a few sparse comments in Etherboot's
49 * SLAM packets use three types of data field:
51 * Nul : A single NUL (0) byte, used as a list terminator
53 * Raw : A block of raw data
55 * Int : A variable-length integer, in big-endian order. The length
56 * of the integer is encoded in the most significant three bits.
58 * Packets received by the client have the following layout:
60 * Int : Transaction identifier. This is an opaque value.
62 * Int : Total number of bytes in the transfer.
64 * Int : Block size, in bytes.
66 * Int : Packet sequence number within the transfer (if this packet
69 * Raw : Packet data (if this packet contains data).
71 * Packets transmitted by the client consist of a run-length-encoded
72 * representation of the received-blocks bitmap, looking something
75 * Int : Number of consecutive successfully-received packets
76 * Int : Number of consecutive missing packets
77 * Int : Number of consecutive successfully-received packets
78 * Int : Number of consecutive missing packets
84 FEATURE ( FEATURE_PROTOCOL, "SLAM", DHCP_EB_FEATURE_SLAM, 1 );
86 /** Default SLAM server port */
87 #define SLAM_DEFAULT_PORT 10000
89 /** Default SLAM multicast IP address */
90 #define SLAM_DEFAULT_MULTICAST_IP \
91 ( ( 239 << 24 ) | ( 255 << 16 ) | ( 1 << 8 ) | ( 1 << 0 ) )
93 /** Default SLAM multicast port */
94 #define SLAM_DEFAULT_MULTICAST_PORT 10000
96 /** Maximum SLAM header length */
97 #define SLAM_MAX_HEADER_LEN ( 7 /* transaction id */ + 7 /* total_bytes */ + \
100 /** Maximum number of blocks to request per NACK
102 * This is a policy decision equivalent to selecting a TCP window
105 #define SLAM_MAX_BLOCKS_PER_NACK 4
107 /** Maximum SLAM NACK length
109 * We only ever send a NACK for a single range of up to @c
110 * SLAM_MAX_BLOCKS_PER_NACK blocks.
112 #define SLAM_MAX_NACK_LEN ( 7 /* block */ + 7 /* #blocks */ + 1 /* NUL */ )
114 /** SLAM slave timeout */
115 #define SLAM_SLAVE_TIMEOUT ( 1 * TICKS_PER_SEC )
117 /** A SLAM request */
118 struct slam_request {
119 /** Reference counter */
120 struct refcnt refcnt;
122 /** Data transfer interface */
123 struct interface xfer;
124 /** Unicast socket */
125 struct interface socket;
126 /** Multicast socket */
127 struct interface mc_socket;
129 /** Master client retry timer */
130 struct retry_timer master_timer;
131 /** Slave client retry timer */
132 struct retry_timer slave_timer;
135 uint8_t header[SLAM_MAX_HEADER_LEN];
136 /** Size of cached header */
138 /** Total number of bytes in transfer */
139 unsigned long total_bytes;
140 /** Transfer block size */
141 unsigned long block_size;
142 /** Number of blocks in transfer */
143 unsigned long num_blocks;
145 struct bitmap bitmap;
146 /** NACK sent flag */
151 * Free a SLAM request
153 * @v refcnt Reference counter
155 static void slam_free ( struct refcnt *refcnt ) {
156 struct slam_request *slam =
157 container_of ( refcnt, struct slam_request, refcnt );
159 bitmap_free ( &slam->bitmap );
164 * Mark SLAM request as complete
166 * @v slam SLAM request
167 * @v rc Return status code
169 static void slam_finished ( struct slam_request *slam, int rc ) {
170 static const uint8_t slam_disconnect[] = { 0 };
172 DBGC ( slam, "SLAM %p finished with status code %d (%s)\n",
173 slam, rc, strerror ( rc ) );
175 /* Send a disconnect message if we ever sent anything to the
178 if ( slam->nack_sent ) {
179 xfer_deliver_raw ( &slam->socket, slam_disconnect,
180 sizeof ( slam_disconnect ) );
183 /* Stop the retry timers */
184 stop_timer ( &slam->master_timer );
185 stop_timer ( &slam->slave_timer );
187 /* Close all data transfer interfaces */
188 intf_shutdown ( &slam->socket, rc );
189 intf_shutdown ( &slam->mc_socket, rc );
190 intf_shutdown ( &slam->xfer, rc );
193 /****************************************************************************
200 * Add a variable-length value to a SLAM packet
202 * @v slam SLAM request
203 * @v iobuf I/O buffer
204 * @v value Value to add
205 * @ret rc Return status code
207 * Adds a variable-length value to the end of an I/O buffer. Will
208 * always leave at least one byte of tailroom in the I/O buffer (to
209 * allow space for the terminating NUL).
211 static int slam_put_value ( struct slam_request *slam,
212 struct io_buffer *iobuf, unsigned long value ) {
217 /* Calculate variable length required to store value. Always
218 * leave at least one byte in the I/O buffer.
220 len = ( ( flsl ( value ) + 10 ) / 8 );
221 if ( len >= iob_tailroom ( iobuf ) ) {
222 DBGC2 ( slam, "SLAM %p cannot add %zd-byte value\n",
226 /* There is no valid way within the protocol that we can end
227 * up trying to push a full-sized long (i.e. without space for
228 * the length encoding).
230 assert ( len <= sizeof ( value ) );
233 data = iob_put ( iobuf, len );
234 for ( i = len ; i-- ; ) {
238 *data |= ( len << 5 );
239 assert ( value == 0 );
245 * Send SLAM NACK packet
247 * @v slam SLAM request
248 * @ret rc Return status code
250 static int slam_tx_nack ( struct slam_request *slam ) {
251 struct io_buffer *iobuf;
252 unsigned long first_block;
253 unsigned long num_blocks;
257 /* Mark NACK as sent, so that we know we have to disconnect later */
260 /* Allocate I/O buffer */
261 iobuf = xfer_alloc_iob ( &slam->socket, SLAM_MAX_NACK_LEN );
263 DBGC ( slam, "SLAM %p could not allocate I/O buffer\n",
268 /* Construct NACK. We always request only a single packet;
269 * this allows us to force multicast-TFTP-style flow control
270 * on the SLAM server, which will otherwise just blast the
271 * data out as fast as it can. On a gigabit network, without
272 * RX checksumming, this would inevitably cause packet drops.
274 first_block = bitmap_first_gap ( &slam->bitmap );
275 for ( num_blocks = 1 ; ; num_blocks++ ) {
276 if ( num_blocks >= SLAM_MAX_BLOCKS_PER_NACK )
278 if ( ( first_block + num_blocks ) >= slam->num_blocks )
280 if ( bitmap_test ( &slam->bitmap,
281 ( first_block + num_blocks ) ) )
285 DBGCP ( slam, "SLAM %p transmitting NACK for blocks "
286 "%ld-%ld\n", slam, first_block,
287 ( first_block + num_blocks - 1 ) );
289 DBGC ( slam, "SLAM %p transmitting initial NACK for blocks "
290 "0-%ld\n", slam, ( num_blocks - 1 ) );
292 if ( ( rc = slam_put_value ( slam, iobuf, first_block ) ) != 0 )
294 if ( ( rc = slam_put_value ( slam, iobuf, num_blocks ) ) != 0 )
296 nul = iob_put ( iobuf, 1 );
299 /* Transmit packet */
300 return xfer_deliver_iob ( &slam->socket, iobuf );
304 * Handle SLAM master client retry timer expiry
306 * @v timer Master retry timer
307 * @v fail Failure indicator
309 static void slam_master_timer_expired ( struct retry_timer *timer,
311 struct slam_request *slam =
312 container_of ( timer, struct slam_request, master_timer );
315 /* Allow timer to stop running. We will terminate the
316 * connection only if the slave timer times out.
318 DBGC ( slam, "SLAM %p giving up acting as master client\n",
321 /* Retransmit NACK */
322 start_timer ( timer );
323 slam_tx_nack ( slam );
328 * Handle SLAM slave client retry timer expiry
330 * @v timer Master retry timer
331 * @v fail Failure indicator
333 static void slam_slave_timer_expired ( struct retry_timer *timer,
335 struct slam_request *slam =
336 container_of ( timer, struct slam_request, slave_timer );
339 /* Terminate connection */
340 slam_finished ( slam, -ETIMEDOUT );
342 /* Try sending a NACK */
343 DBGC ( slam, "SLAM %p trying to become master client\n",
345 start_timer ( timer );
346 slam_tx_nack ( slam );
350 /****************************************************************************
357 * Read and strip a variable-length value from a SLAM packet
359 * @v slam SLAM request
360 * @v iobuf I/O buffer
361 * @v value Value to fill in, or NULL to ignore value
362 * @ret rc Return status code
364 * Reads a variable-length value from the start of the I/O buffer.
366 static int slam_pull_value ( struct slam_request *slam,
367 struct io_buffer *iobuf,
368 unsigned long *value ) {
373 if ( iob_len ( iobuf ) == 0 ) {
374 DBGC ( slam, "SLAM %p empty value\n", slam );
378 /* Read and verify length of value */
380 len = ( *data >> 5 );
382 ( value && ( len > sizeof ( *value ) ) ) ) {
383 DBGC ( slam, "SLAM %p invalid value length %zd bytes\n",
387 if ( len > iob_len ( iobuf ) ) {
388 DBGC ( slam, "SLAM %p value extends beyond I/O buffer\n",
394 iob_pull ( iobuf, len );
395 *value = ( *data & 0x1f );
405 * Read and strip SLAM header
407 * @v slam SLAM request
408 * @v iobuf I/O buffer
409 * @ret rc Return status code
411 static int slam_pull_header ( struct slam_request *slam,
412 struct io_buffer *iobuf ) {
413 void *header = iobuf->data;
416 /* If header matches cached header, just pull it and return */
417 if ( ( slam->header_len <= iob_len ( iobuf ) ) &&
418 ( memcmp ( slam->header, iobuf->data, slam->header_len ) == 0 )){
419 iob_pull ( iobuf, slam->header_len );
423 DBGC ( slam, "SLAM %p detected changed header; resetting\n", slam );
425 /* Read and strip transaction ID, total number of bytes, and
428 if ( ( rc = slam_pull_value ( slam, iobuf, NULL ) ) != 0 )
430 if ( ( rc = slam_pull_value ( slam, iobuf,
431 &slam->total_bytes ) ) != 0 )
433 if ( ( rc = slam_pull_value ( slam, iobuf,
434 &slam->block_size ) ) != 0 )
437 /* Update the cached header */
438 slam->header_len = ( iobuf->data - header );
439 assert ( slam->header_len <= sizeof ( slam->header ) );
440 memcpy ( slam->header, header, slam->header_len );
442 /* Calculate number of blocks */
443 slam->num_blocks = ( ( slam->total_bytes + slam->block_size - 1 ) /
446 DBGC ( slam, "SLAM %p has total bytes %ld, block size %ld, num "
447 "blocks %ld\n", slam, slam->total_bytes, slam->block_size,
450 /* Discard and reset the bitmap */
451 bitmap_free ( &slam->bitmap );
452 memset ( &slam->bitmap, 0, sizeof ( slam->bitmap ) );
454 /* Allocate a new bitmap */
455 if ( ( rc = bitmap_resize ( &slam->bitmap,
456 slam->num_blocks ) ) != 0 ) {
457 /* Failure to allocate a bitmap is fatal */
458 DBGC ( slam, "SLAM %p could not allocate bitmap for %ld "
459 "blocks: %s\n", slam, slam->num_blocks,
461 slam_finished ( slam, rc );
465 /* Notify recipient of file size */
466 xfer_seek ( &slam->xfer, slam->total_bytes );
472 * Receive SLAM data packet
474 * @v slam SLAM request
475 * @v iobuf I/O buffer
476 * @ret rc Return status code
478 static int slam_mc_socket_deliver ( struct slam_request *slam,
479 struct io_buffer *iobuf,
480 struct xfer_metadata *rx_meta __unused ) {
481 struct xfer_metadata meta;
482 unsigned long packet;
486 /* Stop the master client timer. Restart the slave client timer. */
487 stop_timer ( &slam->master_timer );
488 stop_timer ( &slam->slave_timer );
489 start_timer_fixed ( &slam->slave_timer, SLAM_SLAVE_TIMEOUT );
491 /* Read and strip packet header */
492 if ( ( rc = slam_pull_header ( slam, iobuf ) ) != 0 )
495 /* Read and strip packet number */
496 if ( ( rc = slam_pull_value ( slam, iobuf, &packet ) ) != 0 )
499 /* Sanity check packet number */
500 if ( packet >= slam->num_blocks ) {
501 DBGC ( slam, "SLAM %p received out-of-range packet %ld "
502 "(num_blocks=%ld)\n", slam, packet, slam->num_blocks );
507 /* Sanity check length */
508 len = iob_len ( iobuf );
509 if ( len > slam->block_size ) {
510 DBGC ( slam, "SLAM %p received oversize packet of %zd bytes "
511 "(block_size=%ld)\n", slam, len, slam->block_size );
515 if ( ( packet != ( slam->num_blocks - 1 ) ) &&
516 ( len < slam->block_size ) ) {
517 DBGC ( slam, "SLAM %p received short packet of %zd bytes "
518 "(block_size=%ld)\n", slam, len, slam->block_size );
523 /* If we have already seen this packet, discard it */
524 if ( bitmap_test ( &slam->bitmap, packet ) ) {
528 /* Pass to recipient */
529 memset ( &meta, 0, sizeof ( meta ) );
530 meta.flags = XFER_FL_ABS_OFFSET;
531 meta.offset = ( packet * slam->block_size );
532 if ( ( rc = xfer_deliver ( &slam->xfer, iobuf, &meta ) ) != 0 )
535 /* Mark block as received */
536 bitmap_set ( &slam->bitmap, packet );
538 /* If we have received all blocks, terminate */
539 if ( bitmap_full ( &slam->bitmap ) )
540 slam_finished ( slam, 0 );
552 * Receive SLAM non-data packet
554 * @v slam SLAM request
555 * @v iobuf I/O buffer
556 * @ret rc Return status code
558 static int slam_socket_deliver ( struct slam_request *slam,
559 struct io_buffer *iobuf,
560 struct xfer_metadata *rx_meta __unused ) {
563 /* Restart the master client timer */
564 stop_timer ( &slam->master_timer );
565 start_timer ( &slam->master_timer );
567 /* Read and strip packet header */
568 if ( ( rc = slam_pull_header ( slam, iobuf ) ) != 0 )
572 if ( iob_len ( iobuf ) != 0 ) {
573 DBGC ( slam, "SLAM %p received trailing garbage:\n", slam );
574 DBGC_HD ( slam, iobuf->data, iob_len ( iobuf ) );
582 /* Send NACK in reply */
583 slam_tx_nack ( slam );
593 /** SLAM unicast socket interface operations */
594 static struct interface_operation slam_socket_operations[] = {
595 INTF_OP ( xfer_deliver, struct slam_request *, slam_socket_deliver ),
596 INTF_OP ( intf_close, struct slam_request *, slam_finished ),
599 /** SLAM unicast socket interface descriptor */
600 static struct interface_descriptor slam_socket_desc =
601 INTF_DESC ( struct slam_request, socket, slam_socket_operations );
603 /** SLAM multicast socket interface operations */
604 static struct interface_operation slam_mc_socket_operations[] = {
605 INTF_OP ( xfer_deliver, struct slam_request *, slam_mc_socket_deliver ),
606 INTF_OP ( intf_close, struct slam_request *, slam_finished ),
609 /** SLAM multicast socket interface descriptor */
610 static struct interface_descriptor slam_mc_socket_desc =
611 INTF_DESC ( struct slam_request, mc_socket, slam_mc_socket_operations );
613 /****************************************************************************
615 * Data transfer interface
619 /** SLAM data transfer interface operations */
620 static struct interface_operation slam_xfer_operations[] = {
621 INTF_OP ( intf_close, struct slam_request *, slam_finished ),
624 /** SLAM data transfer interface descriptor */
625 static struct interface_descriptor slam_xfer_desc =
626 INTF_DESC ( struct slam_request, xfer, slam_xfer_operations );
629 * Parse SLAM URI multicast address
631 * @v slam SLAM request
632 * @v path Path portion of x-slam:// URI
633 * @v address Socket address to fill in
634 * @ret rc Return status code
636 static int slam_parse_multicast_address ( struct slam_request *slam,
638 struct sockaddr_in *address ) {
639 char path_dup[ strlen ( path ) /* no +1 */ ];
643 /* Create temporary copy of path, minus the leading '/' */
644 assert ( *path == '/' );
645 memcpy ( path_dup, ( path + 1 ) , sizeof ( path_dup ) );
647 /* Parse port, if present */
648 sep = strchr ( path_dup, ':' );
651 address->sin_port = htons ( strtoul ( sep, &end, 0 ) );
652 if ( *end != '\0' ) {
653 DBGC ( slam, "SLAM %p invalid multicast port "
654 "\"%s\"\n", slam, sep );
660 if ( inet_aton ( path_dup, &address->sin_addr ) == 0 ) {
661 DBGC ( slam, "SLAM %p invalid multicast address \"%s\"\n",
670 * Initiate a SLAM request
672 * @v xfer Data transfer interface
673 * @v uri Uniform Resource Identifier
674 * @ret rc Return status code
676 static int slam_open ( struct interface *xfer, struct uri *uri ) {
677 static const struct sockaddr_in default_multicast = {
678 .sin_family = AF_INET,
679 .sin_port = htons ( SLAM_DEFAULT_MULTICAST_PORT ),
680 .sin_addr = { htonl ( SLAM_DEFAULT_MULTICAST_IP ) },
682 struct slam_request *slam;
683 struct sockaddr_tcpip server;
684 struct sockaddr_in multicast;
691 /* Allocate and populate structure */
692 slam = zalloc ( sizeof ( *slam ) );
695 ref_init ( &slam->refcnt, slam_free );
696 intf_init ( &slam->xfer, &slam_xfer_desc, &slam->refcnt );
697 intf_init ( &slam->socket, &slam_socket_desc, &slam->refcnt );
698 intf_init ( &slam->mc_socket, &slam_mc_socket_desc, &slam->refcnt );
699 timer_init ( &slam->master_timer, slam_master_timer_expired,
701 timer_init ( &slam->slave_timer, slam_slave_timer_expired,
703 /* Fake an invalid cached header of { 0x00, ... } */
704 slam->header_len = 1;
705 /* Fake parameters for initial NACK */
706 slam->num_blocks = 1;
707 if ( ( rc = bitmap_resize ( &slam->bitmap, 1 ) ) != 0 ) {
708 DBGC ( slam, "SLAM %p could not allocate initial bitmap: "
709 "%s\n", slam, strerror ( rc ) );
713 /* Open unicast socket */
714 memset ( &server, 0, sizeof ( server ) );
715 server.st_port = htons ( uri_port ( uri, SLAM_DEFAULT_PORT ) );
716 if ( ( rc = xfer_open_named_socket ( &slam->socket, SOCK_DGRAM,
717 ( struct sockaddr * ) &server,
718 uri->host, NULL ) ) != 0 ) {
719 DBGC ( slam, "SLAM %p could not open unicast socket: %s\n",
720 slam, strerror ( rc ) );
724 /* Open multicast socket */
725 memcpy ( &multicast, &default_multicast, sizeof ( multicast ) );
727 ( ( rc = slam_parse_multicast_address ( slam, uri->path,
728 &multicast ) ) != 0 ) ) {
731 if ( ( rc = xfer_open_socket ( &slam->mc_socket, SOCK_DGRAM,
732 ( struct sockaddr * ) &multicast,
733 ( struct sockaddr * ) &multicast ) ) != 0 ) {
734 DBGC ( slam, "SLAM %p could not open multicast socket: %s\n",
735 slam, strerror ( rc ) );
739 /* Start slave retry timer */
740 start_timer_fixed ( &slam->slave_timer, SLAM_SLAVE_TIMEOUT );
742 /* Attach to parent interface, mortalise self, and return */
743 intf_plug_plug ( &slam->xfer, xfer );
744 ref_put ( &slam->refcnt );
748 slam_finished ( slam, rc );
749 ref_put ( &slam->refcnt );
753 /** SLAM URI opener */
754 struct uri_opener slam_uri_opener __uri_opener = {