Changeset View
Standalone View
sys/netinet/tcp_sack.c
Show First 20 Lines • Show All 339 Lines • ▼ Show 20 Lines | tcp_sackhole_remove(struct tcpcb *tp, struct sackhole *hole) | ||||
/* Free this SACK hole. */ | /* Free this SACK hole. */ | ||||
tcp_sackhole_free(tp, hole); | tcp_sackhole_free(tp, hole); | ||||
} | } | ||||
/* | /* | ||||
* Process cumulative ACK and the TCP SACK option to update the scoreboard. | * Process cumulative ACK and the TCP SACK option to update the scoreboard. | ||||
* tp->snd_holes is an ordered list of holes (oldest to newest, in terms of | * tp->snd_holes is an ordered list of holes (oldest to newest, in terms of | ||||
* the sequence space). | * the sequence space). | ||||
* Returns 1 if incoming ACK has previously unknown SACK information, | |||||
jtl: Note that this function treats (snd_una, th_ack) as a SACK hole. Therefore, any new ACK should… | |||||
Not Done Inline ActionsRight, any ack that moves snd_una. As I think that is also new sack info. (see above) hiren: Right, any ack that moves snd_una. As I think that is also new sack info. (see above) | |||||
* 0 otherwise. | |||||
*/ | */ | ||||
void | int | ||||
tcp_sack_doack(struct tcpcb *tp, struct tcpopt *to, tcp_seq th_ack) | tcp_sack_doack(struct tcpcb *tp, struct tcpopt *to, tcp_seq th_ack) | ||||
{ | { | ||||
struct sackhole *cur, *temp; | struct sackhole *cur, *temp; | ||||
struct sackblk sack, sack_blocks[TCP_MAX_SACK + 1], *sblkp; | struct sackblk sack, sack_blocks[TCP_MAX_SACK + 1], *sblkp; | ||||
int i, j, num_sack_blks; | int i, j, num_sack_blks, sack_changed; | ||||
INP_WLOCK_ASSERT(tp->t_inpcb); | INP_WLOCK_ASSERT(tp->t_inpcb); | ||||
num_sack_blks = 0; | num_sack_blks = 0; | ||||
sack_changed = 0; | |||||
/* | /* | ||||
* If SND.UNA will be advanced by SEG.ACK, and if SACK holes exist, | * If SND.UNA will be advanced by SEG.ACK, and if SACK holes exist, | ||||
* treat [SND.UNA, SEG.ACK) as if it is a SACK block. | * treat [SND.UNA, SEG.ACK) as if it is a SACK block. | ||||
*/ | */ | ||||
if (SEQ_LT(tp->snd_una, th_ack) && !TAILQ_EMPTY(&tp->snd_holes)) { | if (SEQ_LT(tp->snd_una, th_ack) && !TAILQ_EMPTY(&tp->snd_holes)) { | ||||
sack_blocks[num_sack_blks].start = tp->snd_una; | sack_blocks[num_sack_blks].start = tp->snd_una; | ||||
sack_blocks[num_sack_blks++].end = th_ack; | sack_blocks[num_sack_blks++].end = th_ack; | ||||
} | } | ||||
/* | /* | ||||
* Append received valid SACK blocks to sack_blocks[], but only if we | * Append received valid SACK blocks to sack_blocks[], but only if we | ||||
* received new blocks from the other side. | * received new blocks from the other side. | ||||
*/ | */ | ||||
if (to->to_flags & TOF_SACK) { | if (to->to_flags & TOF_SACK) { | ||||
old_sacked_bytes = tp->sackhint.sacked_bytes; | |||||
tp->sackhint.sacked_bytes = 0; /* reset */ | tp->sackhint.sacked_bytes = 0; /* reset */ | ||||
for (i = 0; i < to->to_nsacks; i++) { | for (i = 0; i < to->to_nsacks; i++) { | ||||
bcopy((to->to_sacks + i * TCPOLEN_SACK), | bcopy((to->to_sacks + i * TCPOLEN_SACK), | ||||
&sack, sizeof(sack)); | &sack, sizeof(sack)); | ||||
sack.start = ntohl(sack.start); | sack.start = ntohl(sack.start); | ||||
sack.end = ntohl(sack.end); | sack.end = ntohl(sack.end); | ||||
if (SEQ_GT(sack.end, sack.start) && | if (SEQ_GT(sack.end, sack.start) && | ||||
SEQ_GT(sack.start, tp->snd_una) && | SEQ_GT(sack.start, tp->snd_una) && | ||||
SEQ_GT(sack.start, th_ack) && | SEQ_GT(sack.start, th_ack) && | ||||
SEQ_LT(sack.start, tp->snd_max) && | SEQ_LT(sack.start, tp->snd_max) && | ||||
SEQ_GT(sack.end, tp->snd_una) && | SEQ_GT(sack.end, tp->snd_una) && | ||||
SEQ_LEQ(sack.end, tp->snd_max)) { | SEQ_LEQ(sack.end, tp->snd_max)) { | ||||
sack_blocks[num_sack_blks++] = sack; | sack_blocks[num_sack_blks++] = sack; | ||||
tp->sackhint.sacked_bytes += | tp->sackhint.sacked_bytes += | ||||
(sack.end-sack.start); | (sack.end-sack.start); | ||||
} | } | ||||
} | } | ||||
} | } | ||||
/* | /* | ||||
* Return if SND.UNA is not advanced and no valid SACK block is | * Return if SND.UNA is not advanced and no valid SACK block is | ||||
* received. | * received. | ||||
Not Done Inline ActionsThis line appears to calculate the difference between the number of bytes covered by SACK options included with subsequent packets. However, these numbers are not directly comparable. In particular, each segment only includes SACKs for the four most recently-received data blocks. It is possible for consecutive ACKs to contain SACK blocks that cover the same amount of data, but which actually SACK different data. For example, both of these ACKs cover 1000 bytes:
However, because ACK #2 covers an additional SACK block, this SACK contains additional information and may count as a duplicate ACK under either RFC 5681 or RFC 6675. Also, it is possible for ACKs to arrive out of order. In that case, you might process an ACK with three 512-byte SACKs just before an ACK with two 512-byte SACKs. The second ACK might actually have been sent first. Because the second ACK is an "old ACK" by the time it arrive, it probably should not count as a duplicate ACK. For purposes of RFC 6675 (if that's what you're aiming to support), you probably need to modify the scoreboard processing to increment a counter when bytes from a hole are SACKed. jtl: This line appears to calculate the difference between the number of bytes covered by SACK… | |||||
Not Done Inline ActionsYou caught me. I was cheating by adding this as I had it in my PRR (Proportional Rate Reduction) patch that I am working on. In that I need this changed bytes. But yes, your example is clear and something I did think about and ignored. Also, all we want to know is if we got new information or not. We don't really care about number of bytes here for the purpose of this change. I'll go back to the approach that Randall and I discussed before of making tcp_sack_doack() return 'true' when there is new data in incoming SACK information. I believe that should serve the purpose here. WRT oldack, the code right now resets dupack counter to 0 when ad oldack arrives. I am planning to change that so that it ignores oldacks. No increment, no reset. hiren: You caught me. I was cheating by adding this as I had it in my PRR (Proportional Rate… | |||||
*/ | */ | ||||
if (num_sack_blks == 0) | if (num_sack_blks == 0) | ||||
return; | return (sack_changed); | ||||
/* | /* | ||||
* Sort the SACK blocks so we can update the scoreboard with just one | * Sort the SACK blocks so we can update the scoreboard with just one | ||||
* pass. The overhead of sorting upto 4+1 elements is less than | * pass. The overhead of sorting upto 4+1 elements is less than | ||||
* making upto 4+1 passes over the scoreboard. | * making upto 4+1 passes over the scoreboard. | ||||
*/ | */ | ||||
for (i = 0; i < num_sack_blks; i++) { | for (i = 0; i < num_sack_blks; i++) { | ||||
for (j = i + 1; j < num_sack_blks; j++) { | for (j = i + 1; j < num_sack_blks; j++) { | ||||
Show All 34 Lines | if (SEQ_LT(tp->snd_fack, sblkp->start)) { | ||||
* blocks are also beyond the current fack, they will be | * blocks are also beyond the current fack, they will be | ||||
* inserted by way of hole splitting in the while-loop below. | * inserted by way of hole splitting in the while-loop below. | ||||
*/ | */ | ||||
temp = tcp_sackhole_insert(tp, tp->snd_fack,sblkp->start,NULL); | temp = tcp_sackhole_insert(tp, tp->snd_fack,sblkp->start,NULL); | ||||
if (temp != NULL) { | if (temp != NULL) { | ||||
tp->snd_fack = sblkp->end; | tp->snd_fack = sblkp->end; | ||||
/* Go to the previous sack block. */ | /* Go to the previous sack block. */ | ||||
sblkp--; | sblkp--; | ||||
sack_changed = 1; | |||||
} else { | } else { | ||||
/* | /* | ||||
* We failed to add a new hole based on the current | * We failed to add a new hole based on the current | ||||
* sack block. Skip over all the sack blocks that | * sack block. Skip over all the sack blocks that | ||||
* fall completely to the right of snd_fack and | * fall completely to the right of snd_fack and | ||||
* proceed to trim the scoreboard based on the | * proceed to trim the scoreboard based on the | ||||
* remaining sack blocks. This also trims the | * remaining sack blocks. This also trims the | ||||
* scoreboard for th_ack (which is sack_blocks[0]). | * scoreboard for th_ack (which is sack_blocks[0]). | ||||
*/ | */ | ||||
while (sblkp >= sack_blocks && | while (sblkp >= sack_blocks && | ||||
SEQ_LT(tp->snd_fack, sblkp->start)) | SEQ_LT(tp->snd_fack, sblkp->start)) | ||||
sblkp--; | sblkp--; | ||||
if (sblkp >= sack_blocks && | if (sblkp >= sack_blocks && | ||||
SEQ_LT(tp->snd_fack, sblkp->end)) | SEQ_LT(tp->snd_fack, sblkp->end)) | ||||
tp->snd_fack = sblkp->end; | tp->snd_fack = sblkp->end; | ||||
} | } | ||||
} else if (SEQ_LT(tp->snd_fack, sblkp->end)) | } else if (SEQ_LT(tp->snd_fack, sblkp->end)) { | ||||
/* fack is advanced. */ | /* fack is advanced. */ | ||||
tp->snd_fack = sblkp->end; | tp->snd_fack = sblkp->end; | ||||
sack_changed = 1; | |||||
} | |||||
/* We must have at least one SACK hole in scoreboard. */ | /* We must have at least one SACK hole in scoreboard. */ | ||||
KASSERT(!TAILQ_EMPTY(&tp->snd_holes), | KASSERT(!TAILQ_EMPTY(&tp->snd_holes), | ||||
("SACK scoreboard must not be empty")); | ("SACK scoreboard must not be empty")); | ||||
cur = TAILQ_LAST(&tp->snd_holes, sackhole_head); /* Last SACK hole. */ | cur = TAILQ_LAST(&tp->snd_holes, sackhole_head); /* Last SACK hole. */ | ||||
/* | /* | ||||
* Since the incoming sack blocks are sorted, we can process them | * Since the incoming sack blocks are sorted, we can process them | ||||
* making one sweep of the scoreboard. | * making one sweep of the scoreboard. | ||||
*/ | */ | ||||
Show All 12 Lines | if (SEQ_LEQ(sblkp->end, cur->start)) { | ||||
* previous hole. | * previous hole. | ||||
*/ | */ | ||||
cur = TAILQ_PREV(cur, sackhole_head, scblink); | cur = TAILQ_PREV(cur, sackhole_head, scblink); | ||||
continue; | continue; | ||||
} | } | ||||
tp->sackhint.sack_bytes_rexmit -= (cur->rxmit - cur->start); | tp->sackhint.sack_bytes_rexmit -= (cur->rxmit - cur->start); | ||||
KASSERT(tp->sackhint.sack_bytes_rexmit >= 0, | KASSERT(tp->sackhint.sack_bytes_rexmit >= 0, | ||||
("sackhint bytes rtx >= 0")); | ("sackhint bytes rtx >= 0")); | ||||
sack_changed = 1; | |||||
if (SEQ_LEQ(sblkp->start, cur->start)) { | if (SEQ_LEQ(sblkp->start, cur->start)) { | ||||
/* Data acks at least the beginning of hole. */ | /* Data acks at least the beginning of hole. */ | ||||
if (SEQ_GEQ(sblkp->end, cur->end)) { | if (SEQ_GEQ(sblkp->end, cur->end)) { | ||||
/* Acks entire hole, so delete hole. */ | /* Acks entire hole, so delete hole. */ | ||||
temp = cur; | temp = cur; | ||||
cur = TAILQ_PREV(cur, sackhole_head, scblink); | cur = TAILQ_PREV(cur, sackhole_head, scblink); | ||||
tcp_sackhole_remove(tp, temp); | tcp_sackhole_remove(tp, temp); | ||||
/* | /* | ||||
Show All 39 Lines | while (sblkp >= sack_blocks && cur != NULL) { | ||||
* we're done with the sack block or the sack hole. | * we're done with the sack block or the sack hole. | ||||
* Accordingly, we advance one or the other. | * Accordingly, we advance one or the other. | ||||
*/ | */ | ||||
if (SEQ_LEQ(sblkp->start, cur->start)) | if (SEQ_LEQ(sblkp->start, cur->start)) | ||||
cur = TAILQ_PREV(cur, sackhole_head, scblink); | cur = TAILQ_PREV(cur, sackhole_head, scblink); | ||||
else | else | ||||
sblkp--; | sblkp--; | ||||
} | } | ||||
return (sack_changed); | |||||
} | } | ||||
/* | /* | ||||
* Free all SACK holes to clear the scoreboard. | * Free all SACK holes to clear the scoreboard. | ||||
*/ | */ | ||||
void | void | ||||
tcp_free_sackholes(struct tcpcb *tp) | tcp_free_sackholes(struct tcpcb *tp) | ||||
{ | { | ||||
▲ Show 20 Lines • Show All 136 Lines • Show Last 20 Lines |
Note that this function treats (snd_una, th_ack) as a SACK hole. Therefore, any new ACK should cause it to return 1.