From: Sven Eckelmann <[email protected]> When batadv_tp_handle_out_of_order() searches the already existing list of unacked packets, it can often find an entry to merge with. In this case, it would be a waste of time and resources to allocate a batadv_tp_unacked which is then immediately freed again.
Instead, search first through the list. Only when no mergeable entry could be found, it is necessary to record the place to allocate+store the new entry. Signed-off-by: Sven Eckelmann <[email protected]> Signed-off-by: Simon Wunderlich <[email protected]> --- net/batman-adv/tp_meter.c | 88 ++++++++++++++++++--------------------- 1 file changed, 41 insertions(+), 47 deletions(-) diff --git a/net/batman-adv/tp_meter.c b/net/batman-adv/tp_meter.c index ffd3171d4b992..00467aa79de9d 100644 --- a/net/batman-adv/tp_meter.c +++ b/net/batman-adv/tp_meter.c @@ -1417,26 +1417,15 @@ static bool batadv_tp_handle_out_of_order(struct batadv_tp_receiver *tp_vars, u32 seqno, u32 payload_len) __must_hold(&tp_vars->ack_seqno_lock) { - struct batadv_tp_unacked *un, *new; + struct list_head *pos = &tp_vars->unacked_list; + struct batadv_tp_unacked *new = NULL; + u32 end_seqno = seqno + payload_len; struct batadv_tp_unacked *safe; - bool added = false; - - new = kmalloc_obj(*new, GFP_ATOMIC); - if (unlikely(!new)) - return false; - - new->seqno = seqno; - new->len = payload_len; - - /* if the list is empty immediately attach this new object */ - if (list_empty(&tp_vars->unacked_list)) { - list_add(&new->list, &tp_vars->unacked_list); - tp_vars->unacked_count++; - return true; - } + struct batadv_tp_unacked *un; - /* otherwise loop over the list and either drop the packet because this - * is a duplicate or store it at the right position. + /* loop over the list to find either an existing entry which the new + * seqno range can be merged with or the position at which a new entry + * has to be inserted. * * The iteration is done in the reverse way because it is likely that * the last received packet (the one being processed now) has a bigger @@ -1444,7 +1433,7 @@ static bool batadv_tp_handle_out_of_order(struct batadv_tp_receiver *tp_vars, */ list_for_each_entry_reverse(un, &tp_vars->unacked_list, list) { /* look for the right position - an un which is smaller */ - if (batadv_seq_before(new->seqno, un->seqno)) + if (batadv_seq_before(seqno, un->seqno)) continue; /* smaller/equal seqno was found but they might be directly @@ -1452,62 +1441,67 @@ static bool batadv_tp_handle_out_of_order(struct batadv_tp_receiver *tp_vars, * * It is already known that: * - * un->seqno <= new->seqno + * un->seqno <= seqno * * When establishing that: * - * new->seqno <= un->seqno + un->len + * seqno <= un->seqno + un->len * * Then it is not necessary to add a new entry because the * smaller/equal seqno of un might already contain the new * received packet or we only add new data directly after * the end of un. The latter can be identified using: * - * un->seqno + un->len <= new->seqno + new->len + * un->seqno + un->len <= end_seqno */ - if (!batadv_seq_before(un->seqno + un->len, new->seqno)) { + if (!batadv_seq_before(un->seqno + un->len, seqno)) { /* new data directly after un? */ - if (!batadv_seq_before(new->seqno + new->len, - un->seqno + un->len)) - un->len = new->seqno + new->len - un->seqno; + if (!batadv_seq_before(end_seqno, un->seqno + un->len)) + un->len = end_seqno - un->seqno; - /* un now represents both old un + new */ - kfree(new); - added = true; - - /* un has to be used to check if the gap to the next - * seqno range was closed + /* un now represents both old un + new range and has to + * be used to check if the gap to the next seqno range + * was closed */ new = un; - break; + } else { + /* as soon as an entry having a smaller seqno is found, + * the new one is attached _after_ it. In this way the + * list is kept in ascending order + */ + pos = &un->list; } - /* as soon as an entry having a smaller seqno is found, the new - * one is attached _after_ it. In this way the list is kept in - * ascending order - */ - list_add(&new->list, &un->list); - added = true; - tp_vars->unacked_count++; break; } - /* received packet with smallest seqno out of order; add it to front */ - if (!added) { - list_add(&new->list, &tp_vars->unacked_list); + /* no entry to merge with was found; insert a new one after the entry + * with the next smaller seqno (or at the front of the list when the + * new seqno is the smallest or the list is empty) + */ + if (!new) { + new = kmalloc_obj(*new, GFP_ATOMIC); + if (unlikely(!new)) + return false; + + new->seqno = seqno; + new->len = payload_len; + + list_add(&new->list, pos); tp_vars->unacked_count++; } /* check if new filled the gap to the next list entries */ un = new; list_for_each_entry_safe_continue(un, safe, &tp_vars->unacked_list, list) { - if (batadv_seq_before(new->seqno + new->len, un->seqno)) + if (batadv_seq_before(end_seqno, un->seqno)) break; /* next entry is overlapping or adjacent - combine both */ - if (batadv_seq_before(new->seqno + new->len, - un->seqno + un->len)) - new->len = un->seqno + un->len - new->seqno; + if (batadv_seq_before(end_seqno, un->seqno + un->len)) { + end_seqno = un->seqno + un->len; + new->len = end_seqno - new->seqno; + } list_del(&un->list); kfree(un); -- 2.47.3
