[PATCH 5/6]: Add history query/lookup function

[PATCH 5/6]: Add history query/lookup function

[Gerrit Renker]

[TFRC]: Add history query/lookup function

This completes the basic TX history functions that are implemented by this
patch set, by adding a lock-protected lookup function to look up the send
time of a particular sent packet.

Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
---
 net/dccp/ccids/lib/packet_history.c |   44 ++++++++++++++++++++++--------------
 net/dccp/ccids/lib/packet_history.h |    4 ---
 2 files changed, 29 insertions(+), 19 deletions(-)

--- a/net/dccp/ccids/lib/packet_history.h
+++ b/net/dccp/ccids/lib/packet_history.h
@@ -86,10 +86,8 @@ static inline void tfrc_tx_hist_init(str
 	head->cache = cache;
 }
 
-extern struct dccp_tx_hist_entry *
-			dccp_tx_hist_find_entry(const struct list_head *list,
-						const u64 seq);
 extern int  tfrc_tx_hist_add(struct tfrc_tx_hist_head *head, u64 seqno);
+extern int  tfrc_tx_hist_when(ktime_t *, struct tfrc_tx_hist_head *, u64);
 extern void tfrc_tx_hist_cleanup(struct tfrc_tx_hist_head *head);
 
 /*
--- a/net/dccp/ccids/lib/packet_history.c
+++ b/net/dccp/ccids/lib/packet_history.c
@@ -74,22 +74,6 @@ void tfrc_tx_cache_cleanup(struct kmem_c
 }
 EXPORT_SYMBOL_GPL(tfrc_tx_cache_cleanup);
 
-struct dccp_tx_hist_entry *
-	dccp_tx_hist_find_entry(const struct list_head *list, const u64 seq)
-{
-	struct dccp_tx_hist_entry *packet = NULL, *entry;
-
-	list_for_each_entry(entry, list, dccphtx_node)
-		if (entry->dccphtx_seqno = seq) {
-			packet = entry;
-			break;
-		}
-
-	return packet;
-}
-
-EXPORT_SYMBOL_GPL(dccp_tx_hist_find_entry);
-
 int tfrc_tx_hist_add(struct tfrc_tx_hist_head *head, u64 seqno)
 {
 	struct tfrc_tx_hist *new = kmem_cache_alloc(head->cache, gfp_any());
@@ -121,6 +105,34 @@ static void __tfrc_tx_hist_remove_tail(s
 	}
 }
 
+/**
+ *  tfrc_tx_hist_when  -  Retrieve send time of past packet
+ *  @stamp: send time to look up (returns value result)
+ *  @head:  TX history to search in
+ *  @ackno: ACK number which indicates the sent packet's sequence number
+ *  If successful, it garbage-collects older (irrelevant) entries and returns 1.
+ */
+int tfrc_tx_hist_when(ktime_t *stamp, struct tfrc_tx_hist_head *head, u64 ackno)
+{
+	struct tfrc_tx_hist *cur, *tail = NULL;
+
+	write_lock_bh(&tfrc_tx_hist_lock);
+	for (cur = head->first; cur != NULL; cur = cur->next)
+		if (cur->seqno = ackno) {
+			*stamp = cur->stamp;
+			tail = cur->next;
+			cur->next = NULL;
+			break;
+		}
+	write_unlock_bh(&tfrc_tx_hist_lock);
+
+	if (tail)
+		__tfrc_tx_hist_remove_tail(tail, head->cache);
+
+	return (cur != NULL);
+}
+EXPORT_SYMBOL_GPL(tfrc_tx_hist_when);
+
 void tfrc_tx_hist_cleanup(struct tfrc_tx_hist_head *head)
 {
 	struct tfrc_tx_hist *free_this;

Re: [PATCH 5/6]: Add history query/lookup function

[Ian McDonald]

On 6/12/07, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> [TFRC]: Add history query/lookup function
>
> This completes the basic TX history functions that are implemented by this
> patch set, by adding a lock-protected lookup function to look up the send
> time of a particular sent packet.

I notice there is other functionality here also...

> +/**
> + *  tfrc_tx_hist_when  -  Retrieve send time of past packet
> + *  If successful, it garbage-collects older (irrelevant) entries and returns 1.
> + */
> +int tfrc_tx_hist_when(ktime_t *stamp, struct tfrc_tx_hist_head *head, u64 ackno)
> +{
> +
> +       if (tail)
> +               __tfrc_tx_hist_remove_tail(tail, head->cache);
> +

Can you explain the rationale behind this?

Ian
-- 
Web: http://wand.net.nz/~iam4/
Blog: http://iansblog.jandi.co.nz
WAND Network Research Group

Re: [PATCH 5/6]: Add history query/lookup function

[Ian McDonald]

On 6/17/07, Ian McDonald <ian.mcdonald@jandi.co.nz> wrote:
> On 6/12/07, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> > [TFRC]: Add history query/lookup function
> >
> > This completes the basic TX history functions that are implemented by this
> > patch set, by adding a lock-protected lookup function to look up the send
> > time of a particular sent packet.
>
> I notice there is other functionality here also...
>
And I see why from the following patch now. Perhaps you could add
something to commit description to elude to this.

Signed-off-by: Ian McDonald <ian.mcdonald@jandi.co.nz>
-- 
Web: http://wand.net.nz/~iam4/
Blog: http://iansblog.jandi.co.nz
WAND Network Research Group

Re: [PATCH 5/6]: Add history query/lookup function

[Gerrit Renker]

 |  I notice there is other functionality here also...
|  
|  > +/**
|  > + *  tfrc_tx_hist_when  -  Retrieve send time of past packet
|  > + *  If successful, it garbage-collects older (irrelevant) entries and returns 1.
|  > + */
|  > +int tfrc_tx_hist_when(ktime_t *stamp, struct tfrc_tx_hist_head *head, u64 ackno)
|  > +{
|  > +
|  > +       if (tail)
|  > +               __tfrc_tx_hist_remove_tail(tail, head->cache);
|  > +
|  
|  Can you explain the rationale behind this?
|  
You have cut out half of the code, I therefore need to copy again below:

+int tfrc_tx_hist_when(ktime_t *stamp, struct tfrc_tx_hist_head *head, u64 ackno)
+{
+	struct tfrc_tx_hist *cur, *tail = NULL;
+
+	write_lock_bh(&tfrc_tx_hist_lock);
+	for (cur = head->first; cur != NULL; cur = cur->next)
+		if (cur->seqno = ackno) {
+			*stamp = cur->stamp;
+			tail = cur->next;
+			cur->next = NULL;
+			break;
+		}
+	write_unlock_bh(&tfrc_tx_hist_lock);
+
+	if (tail)
+		__tfrc_tx_hist_remove_tail(tail, head->cache);
+
+	return (cur != NULL);
+}

The patch first performs a lookup. If the lookup is successful, tail != NULL and 
all entries older than `cur' (LIFO order) are cut off; at the same time tail is set
to the `tail' starting at the now old/obsolete entries.

Removing the tail is not done when under lock, since this may take time (you never
know how long the list is). So this uses a common trick of first `orphaning' the
old tail, and then doing the cleanup outside the lock-protected region, when there
is more time to do so.

Maybe you have noted that the subsequent patch (6/6) has the following hunk:

@@ -492,9 +488,6 @@ static void ccid3_hc_tx_packet_recv(stru
 		/* unschedule no feedback timer */
 		sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer);
 
-		/* remove all packets older than the one acked from history */
-		dccp_tx_hist_purge_older(ccid3_tx_hist,
-					 &hctx->ccid3hctx_hist, packet);
 		/*
 		 * As we have calculated new ipi, delta, t_nom it is possible
 		 * that we now can send a packet, so wake up dccp_wait_for_ccid

=> The above effectively replaces this in one go. This is better since otherwise
   the same lock would need to be acquired twice - once for reading, then for
   writing (to perform the purge). This would introduce a race condition.
  

=> You can find this also in the documentation of patch 5/6:

+ *  tfrc_tx_hist_when  -  Retrieve send time of past packet
+
+ *  If successful, it garbage-collects older (irrelevant) entries and returns 1.
+ */

Re: [PATCH 5/6]: Add history query/lookup function

[Gerrit Renker]

Quoting Ian McDonald:
|  And I see why from the following patch now. Perhaps you could add
|  something to commit description to elude to this.
Ah coming through to this one - I just answered the other email:)

Yes, I have changed the commit message as follows:

"Note: When the lookup is successful, the function automatically garbage-collects
       older entries (which become at that point useless/irrelevant). 
       This is done outside the lock, to keep lock times to a minimum."


Thanks for going through the patches, I am glad for the feedback.