TCPCT part 1d: generate Responder Cookie

First of all, this is my first attempt at locks, so I'd like early review.

Secondly, scripts/checkpatch.pl tells me:

ERROR: do not initialise statics to 0 or NULL
#95: FILE: net/ipv4/tcp.c:2977:
+static struct tcp_cookie_secret *tcp_secret_generating = NULL;

They need to be NULL, and I'm not planning on exporting them, so what's the preferred mechanism?

(I've grep'd many other instances of statics = 0 or NULL, so I'm not alone.)

Since October 4th, I've repeatedly asked publicly for assistance with these Linux-specific memory locking constructs and cryptography. I've also sent private messages. No help has been forthcoming. None. Nada.

At this point, I've spent weeks re-spinning code that I'd understood was approved a year ago. The whole project should have been finished by now!

So, I'll try a larger audience. Could somebody take a look at my usage of read and write locking?

NB, I'm trying to port some 15-year-old fairly simple and straightforward (single cpu) code from the KA9Q cooperative multitasking platform.

I've examined existing code used for syncookies and TCP MD5 authenticators. Neither meets my needs, as this secret is updated every few minutes. Both have very different approaches. They are rarely used. My code will be used on the order of tens of thousands of connections per second.

Moreover, it seems to my naive eye that the syncookie per cpu code simply doesn't work properly. The workspace is allocated per cpu, but the cpu could change during the extensive SHA1 computations. Bug?

Therefore, I'm approaching this as simply as possible. I'm particularly concerned about the initialization and cache state of memory pointers.

Does the locking handle this? Or is there more to be done?

Quoted 6 lines · William Allen Simpson

Since October 4th, I've repeatedly asked publicly for assistance with these Linux-specific memory locking constructs and cryptography. I've also sent private messages. No help has been forthcoming. None. Nada.

At this point, I've spent weeks re-spinning code that I'd understood was approved a year ago. The whole project should have been finished by now!

Your messages on netdev are two weeks old, not one year, and came during LKS. Many developpers were busy in Japan.

Quoted 11 lines

So, I'll try a larger audience. Could somebody take a look at my usage of read and write locking?

NB, I'm trying to port some 15-year-old fairly simple and straightforward (single cpu) code from the KA9Q cooperative multitasking platform.

I've examined existing code used for syncookies and TCP MD5 authenticators. Neither meets my needs, as this secret is updated every few minutes. Both have very different approaches. They are rarely used. My code will be used on the order of tens of thousands of connections per second.

Quoted 4 lines

Moreover, it seems to my naive eye that the syncookie per cpu code simply doesn't work properly. The workspace is allocated per cpu, but the cpu could change during the extensive SHA1 computations. Bug?

This patch looks fine, but I dont see how this new function is used.

Some points :

1) We are working hard to remove rwlocks from network stack, so please dont add a new one.

add a new one. You probably can use a seqlock or RCU, or a server handling 10.000 connections request per second on many NIC will hit this rwlock.

2)

	} else if (unlikely(time_after(jiffy, tcp_secret_primary->expires))) {
		get_random_bytes(secrets, sizeof(secrets));

		write_lock(&tcp_secret_locker);

It would be better to first get the lock, then get random_bytes, in order not wasting entropy.

3) If you change secret ever 600 seconds, it might be better to use a timer so that you dont have to check expiration and this logic at each SYN packet. (Disociate the lookup (read-only, done many time per second) from the updates (trigerred by a timer every 600 secs))

(Not counting you'll probably need to use a similar lookup algo for the ACK packet coming from client)

Thank you for your helpful comments. I'm not familiar with LKS. Is that a month long project?

The (buggy?) syncookie code that I'm avoiding/replacing is:

static DEFINE_PER_CPU(__u32 [16 + 5 + SHA_WORKSPACE_WORDS],

              ipv4_cookie_scratch);

static u32 cookie_hash(__be32 saddr, __be32 daddr, __be16 sport, __be16 dport,
u32 count, int c)

{
    __u32 *tmp = __get_cpu_var(ipv4_cookie_scratch);

    memcpy(tmp + 4, syncookie_secret[c], sizeof(syncookie_secret[c]));
    tmp[0] = (__force u32)saddr;
    tmp[1] = (__force u32)daddr;
    tmp[2] = ((__force u32)sport << 16) + (__force u32)dport;
    tmp[3] = count;
    sha_transform(tmp + 16, (__u8 *)tmp, tmp + 16 + 5);

    return tmp[17];
}

It appears to me that the operations could be interrupted at any time, and the fairly expensive sha transform (or probably any of the assignments) could be corrupted?

That is, cpu0 grabs a scratch area, copies some data into it, interrupts, cpu0 comes along again with another packet, points into the same workspace, mashes the data, while cpu1 completes the previous operation with the old tmp pointer on the stack.

Worse, this is called twice, each time getting tmp, and mashing the data, and at the same time others are calling it twice more for verification.

Since syncookies only occur under stress, the code isn't well tested, and the only symptom would be the returned packet would be dropped after failing to verify. Since this only happens when lots of packets are arriving, dropped packets probably aren't noticed.

However, that would be unacceptable for my code.

cookie_hash() runs in a non preemptable context. CPU cannot change under us.

(or else, we would not use __get_cpu_var(ipv4_cookie_scratch); )

And of course, each cpu gets its own scratch area, thanks to __get_cpu_var()

Quoted 8 lines · Eric Dumazet

cookie_hash() runs in a non preemptable context. CPU cannot change under us.

(or else, we would not use __get_cpu_var(ipv4_cookie_scratch); )

And of course, each cpu gets its own scratch area, thanks to __get_cpu_var()

Interesting. I'm not sure that running CPU intensive functions like SHA1 in
a non-preemptable context is a good idea. I'd assumed it wasn't!

Perhaps you could point at the documentation in the code that explains this?

Perhaps a function header comment that mentions it?

All I know is (from testing) that the tcp_minisockets.c caller is sometimes called in a fashion that requires atomic allocation, and other times does not!

See my "Subject: query: tcpdump versus atomic?" thread from Oct 14th.

Large part of network code is run by softirq handler, and a softirq handler is not preemptable with another softirq (including itself).

Quoted 1 line

Perhaps a function header comment that mentions it?

So we are going to add a header to thousand of functions repeating this prereq ?

Quoted 3 lines

All I know is (from testing) that the tcp_minisockets.c caller is sometimes called in a fashion that requires atomic allocation, and other times does not!

Maybe callers have different contexts (running from softirq handler or from process context). Atomic ops are expensive and we try to avoid them if/when possible.

Quoted 1 line

See my "Subject: query: tcpdump versus atomic?" thread from Oct 14th.

You probably add a bug in your kernel, leaving a function with unpaired lock/unlock of notallow_something/allow_something

There are books about linux internals that you could read if you want some extra documentation. Dont ask me details, I never read them :)

Quoted 4 lines · Eric Dumazet

Large part of network code is run by softirq handler, and a softirq handler
is not preemptable with another softirq (including itself).

Thank you. That's helpful to know, as some existing locks have a "bh". I've never figured out the ip_local_deliver_finish() context.

Knowing that there can only be one instance of the tcp stack running at any one time, and the cpu never changes even after being interrupted, will make it much easier to code.

Quoted 1 line

(No, I've not yet added locks; obviously, I'm still asking about them.)

Unlikely, as it was easy to reproduce by changing one line, without *any* of
my code present. Usually works, but doesn't work with tcpdump running on the interface:

This patch looks fine, but I dont see how this new function is used.

Some points :

1) We are working hard to remove rwlocks from network stack, so please dont
add a new one. You probably can use a seqlock or RCU, or a server handling 10.000 connections request per second on many NIC will hit this rwlock.

Quoted 4 lines · Eric Dumazet

This patch looks fine, but I dont see how this new function is used.

Some points :

Quoted 6 lines

1) We are working hard to remove rwlocks from network stack, so please dont
add a new one. You probably can use a seqlock or RCU, or a server handling 10.000 connections request per second on many NIC will hit this rwlock.

This is my attempt at using RCU, as seqlock didn't seem to apply (and is missing any Documentation.)

Documentation/RCU/checklist.txt #7 says:

One exception to this rule: rcu_read_lock() and rcu_read_unlock() may be substituted for rcu_read_lock_bh() and rcu_read_unlock_bh() in cases where local bottom halves are already known to be disabled, for example, in irq or softirq context. Commenting such cases is a must, of course! And the jury is still out on whether the increased speed is worth it.

Quoted 6 lines · Eric Dumazet

This patch looks fine, but I dont see how this new function is used. Some points :
1) We are working hard to remove rwlocks from network stack, so please dont
add a new one. You probably can use a seqlock or RCU, or a server handling 10.000 connections request per second on many NIC will hit this rwlock.

This is my attempt at using RCU, as seqlock didn't seem to apply (and is missing any Documentation.)

After the discussion about context, one question that I have is the need for the _bh suffix?

net/ipv4/tcp.c +5 -0

+		rcu_read_lock_bh();
+		memcpy(&xvp->cookie_bakery[0],
+		       &rcu_dereference(tcp_secret_generating)->secrets[0],
+		       sizeof(tcp_secret_generating->secrets));
+		rcu_read_unlock_bh();

Documentation/RCU/checklist.txt #7 says:

One exception to this rule: rcu_read_lock() and rcu_read_unlock() may be substituted for rcu_read_lock_bh() and rcu_read_unlock_bh() in cases where local bottom halves are already known to be disabled, for example, in irq or softirq context. Commenting such cases is a must, of course! And the jury is still out on whether the increased speed is worth it.

include/linux/cryptohash.h +14 -0

+			if (unlikely(tcp_secret_primary->expires ==
+				     tcp_secret_secondary->expires)) {
+				struct timespec tv;
+	
+				getnstimeofday(&tv);
+				secrets[COOKIE_DIGEST_WORDS+0] ^= (u32)tv.tv_nsec;
+				tcp_secret_secondary->expires = jiffy
+							      + TCP_SECRET_1MSL;
+			} else {
+				tcp_secret_secondary->expires = jiffy
+							      + TCP_SECRET_LIFE;
+				tcp_secret_primary->expires = jiffy
+							    + TCP_SECRET_2MSL;
+			}

Quoted 8 lines · William Allen Simpson

Documentation/RCU/checklist.txt #7 says:

One exception to this rule: rcu_read_lock() and rcu_read_unlock() may be substituted for rcu_read_lock_bh() and rcu_read_unlock_bh() in cases where local bottom halves are already known to be disabled, for example, in irq or softirq context. Commenting such cases is a must, of course! And the jury is still out on whether the increased speed is worth it.

I strongly suggest using the matching primitives unless you have a really strong reason not to.

net/ipv4/tcp.c EXPORT_SYMBOL(tcp_md5_hash_key); · line 3040

Quoted 6 lines

net/ipv4/tcp.c +6 -0

+			rcu_assign_pointer(tcp_secret_generating,
+					   tcp_secret_secondary);
+			rcu_assign_pointer(tcp_secret_retiring,
+					   tcp_secret_primary);
+			spin_unlock_bh(&tcp_secret_locker);
+			/* call_rcu() or synchronize_rcu() not needed. */

Would you be willing to say why? Are you relying on a time delay for a given item to pass through tcp_secret_secondary and tcp_secret_retiring or some such? If so, how do you know that this time delay will always be long enough?

Or are you just shuffling the data structures around, without ever freeing them? If so, is it really OK for a given reader to keep a reference to a given item through the full range of shuffling, especially given that it might be accesssing this concurrently with the ->expires assignments above?

Either way, could you please expand the comment to give at least some hint to the poor guy reading your code? ;-)

Yes. Just shuffling the pointers without ever freeing anything. So, there's nothing for call_rcu() to do, and nothing else to synchronize (only the pointers). This assumes that after _unlock_ any CPU cache with an old pointer->expires will hit the _lock_ code, and that will update *both* ->expires and the other array elements concurrently?

Quoted 6 lines · William Allen Simpson

Yes. Just shuffling the pointers without ever freeing anything. So, there's nothing for call_rcu() to do, and nothing else to synchronize (only the pointers). This assumes that after _unlock_ any CPU cache with an old pointer->expires will hit the _lock_ code, and that will update *both* ->expires and the other array elements concurrently?

Reiterating, I've not found Documentation showing that this code works:

net/ipv4/tcp.c +11 -0

+    unsigned long jiffy = jiffies;
+
+    if (unlikely(time_after(jiffy, tcp_secret_generating->expires))) {
+        spin_lock_bh(&tcp_secret_locker);
+        if (!time_after(jiffy, tcp_secret_generating->expires)) {
+            /* refreshed by another */
+            spin_unlock_bh(&tcp_secret_locker);
+            memcpy(&xvp->cookie_bakery[0],
+                   &tcp_secret_generating->secrets[0],
+                   sizeof(tcp_secret_generating->secrets));
+        } else {

How is it ensured that an old tcp_secret_generating or an old ->expires, followed by a spin_lock, has updated both?

And even when both are updated, then every word of the ->secrets array has also been updated in the local cache?

Is this a property of spin_lock()? Or spin_unlock()?

Quoted 10 lines · Paul E. McKenney

Quoted 8 lines · William Allen Simpson

Documentation/RCU/checklist.txt #7 says:

One exception to this rule: rcu_read_lock() and rcu_read_unlock() may be substituted for rcu_read_lock_bh() and rcu_read_unlock_bh() in cases where local bottom halves are already known to be disabled, for example, in irq or softirq context. Commenting such cases is a must, of course! And the jury is still out on whether the increased speed is worth it.

Quoted 3 lines

I strongly suggest using the matching primitives unless you have a really strong reason not to.

Eric gave contrary advice. But he also suggested (in an earlier message) clearing the secrets with a timer, which could be a separate context -- although much later in time.

As you suggest, I'll use the _bh suffix everywhere until every i is dotted and t is crossed. Then, check for efficiency later after thorough analysis by experts such as yourself.

This code will be hit on every SYN and SYNACK that has a cookie option. But it's just prior to a CPU intensive sha_transform -- in comparison, it's trivial.

Quoted 8 lines · William Allen Simpson

As you suggest, I'll use the _bh suffix everywhere until every i is dotted and t is crossed. Then, check for efficiency later after thorough analysis by experts such as yourself.

This code will be hit on every SYN and SYNACK that has a cookie option. But it's just prior to a CPU intensive sha_transform -- in comparison, it's trivial.

I think you misunderstood my advice ;)

Quoted 11 lines · Paul E. McKenney

Quoted 8 lines · William Allen Simpson

Documentation/RCU/checklist.txt #7 says:

One exception to this rule: rcu_read_lock() and rcu_read_unlock() may be substituted for rcu_read_lock_bh() and rcu_read_unlock_bh() in cases where local bottom halves are already known to be disabled, for example, in irq or softirq context. Commenting such cases is a must, of course! And the jury is still out on whether the increased speed is worth it.

I strongly suggest using the matching primitives unless you have a really strong reason not to.

Eric gave contrary advice. But he also suggested (in an earlier message) clearing the secrets with a timer, which could be a separate context -- although much later in time.

As you suggest, I'll use the _bh suffix everywhere until every i is dotted and t is crossed. Then, check for efficiency later after thorough analysis by experts such as yourself.

This code will be hit on every SYN and SYNACK that has a cookie option. But it's just prior to a CPU intensive sha_transform -- in comparison, it's trivial.

Quoted 9 lines

net/ipv4/tcp.c EXPORT_SYMBOL(tcp_md5_hash_key); · line 3040

Quoted 6 lines

net/ipv4/tcp.c +6 -0

+			rcu_assign_pointer(tcp_secret_generating,
+					   tcp_secret_secondary);
+			rcu_assign_pointer(tcp_secret_retiring,
+					   tcp_secret_primary);
+			spin_unlock_bh(&tcp_secret_locker);
+			/* call_rcu() or synchronize_rcu() not needed. */

Would you be willing to say why? Are you relying on a time delay for a given item to pass through tcp_secret_secondary and tcp_secret_retiring or some such? If so, how do you know that this time delay will always

Quoted 8 lines

be long enough?
Or are you just shuffling the data structures around, without ever freeing them? If so, is it really OK for a given reader to keep a reference to a given item through the full range of shuffling, especially given that it might be accesssing this concurrently with the ->expires assignments above?
Either way, could you please expand the comment to give at least some hint to the poor guy reading your code? ;-)

Yes. Just shuffling the pointers without ever freeing anything. So, there's nothing for call_rcu() to do, and nothing else to synchronize (only the pointers). This assumes that after _unlock_ any CPU cache with an old pointer->expires will hit the _lock_ code, and that will update *both* ->expires and the other array elements concurrently?

One of the advantages of this scheme is the new secret is initialized while the old secret is still used, and the old secret can continue to be verified as old packets arrive. (I originally designed this for Photuris [RFC-2522] circa 1995.)

As described in the long header given, each array element goes through four (4) states. This is handling the first state transition. It will hit at least 2 more locks, pointer updates, and unlocks before reuse.

Also, a great deal of time passes. After being retired (and expired), it will be unused for approximately 5 minutes.

All that's a bit long for a comment.

(quoted diff) +6 -0

+			/*
+			 * The retiring data is never freed.  Instead, it is
+			 * replaced after later pointer updates and a quiet
+			 * time of approximately 5 minutes.  There is nothing
+			 * for call_rcu() or synchronize_rcu() to handle.
+			 */

Clear enough?