+/**
+ * Find selective acknowledgement block
+ *
+ * @v tcp TCP connection
+ * @v seq SEQ value in SACK block (in host-endian order)
+ * @v sack SACK block to fill in (in host-endian order)
+ * @ret len Length of SACK block
+ */
+static uint32_t tcp_sack_block ( struct tcp_connection *tcp, uint32_t seq,
+ struct tcp_sack_block *sack ) {
+ struct io_buffer *iobuf;
+ struct tcp_rx_queued_header *tcpqhdr;
+ uint32_t left = tcp->rcv_ack;
+ uint32_t right = left;
+
+ /* Find highest block which does not start after SEQ */
+ list_for_each_entry ( iobuf, &tcp->rx_queue, list ) {
+ tcpqhdr = iobuf->data;
+ if ( tcp_cmp ( tcpqhdr->seq, right ) > 0 ) {
+ if ( tcp_cmp ( tcpqhdr->seq, seq ) > 0 )
+ break;
+ left = tcpqhdr->seq;
+ }
+ if ( tcp_cmp ( tcpqhdr->nxt, right ) > 0 )
+ right = tcpqhdr->nxt;
+ }
+
+ /* Fail if this block does not contain SEQ */
+ if ( tcp_cmp ( right, seq ) < 0 )
+ return 0;
+
+ /* Populate SACK block */
+ sack->left = left;
+ sack->right = right;
+ return ( right - left );
+}
+
+/**
+ * Update TCP selective acknowledgement list
+ *
+ * @v tcp TCP connection
+ * @v seq SEQ value in first SACK block (in host-endian order)
+ * @ret count Number of SACK blocks
+ */
+static unsigned int tcp_sack ( struct tcp_connection *tcp, uint32_t seq ) {
+ struct tcp_sack_block sack[TCP_SACK_MAX];
+ unsigned int old = 0;
+ unsigned int new = 0;
+ unsigned int i;
+ uint32_t len;
+
+ /* Populate first new SACK block */
+ len = tcp_sack_block ( tcp, seq, &sack[0] );
+ if ( len )
+ new++;
+
+ /* Populate remaining new SACK blocks based on old SACK blocks */
+ for ( old = 0 ; old < TCP_SACK_MAX ; old++ ) {
+
+ /* Stop if we run out of space in the new list */
+ if ( new == TCP_SACK_MAX )
+ break;
+
+ /* Skip empty old SACK blocks */
+ if ( tcp->sack[old].left == tcp->sack[old].right )
+ continue;
+
+ /* Populate new SACK block */
+ len = tcp_sack_block ( tcp, tcp->sack[old].left, &sack[new] );
+ if ( len == 0 )
+ continue;
+
+ /* Eliminate duplicates */
+ for ( i = 0 ; i < new ; i++ ) {
+ if ( sack[i].left == sack[new].left ) {
+ new--;
+ break;
+ }
+ }
+ new++;
+ }
+
+ /* Update SACK list */
+ memset ( tcp->sack, 0, sizeof ( tcp->sack ) );
+ memcpy ( tcp->sack, sack, ( new * sizeof ( tcp->sack[0] ) ) );
+ return new;
+}
+