delay accounting & taskstats fixes

Andrew,

Chandra, Balbir & I have been putting taskstats and delay accounting patches through some extensive testing on multiple platforms.

Following are a set of patches that fix some bugs found as well as some cleanups of the code. Some results showing the cpumask feature works as expected will follow separately.

--Shailabh

Patches against 2.6.18-rc1, apply over the per-task delay accounting patches already in 2.6.18-rc1-mm1

Series

per-task-delay-accounting-taskstats-interface-exit-data-through-cpumasks-fix2.patch per-task-delay-accounting-documentation-fix.patch per-task-delay-accounting-taskstats-fix-early-sem-init.patch per-task-delay-accounting-taskstats-fix-drop-listener-only-on-socket-close.patch list_islast.patch per-task-delay-accounting-taskstats-fix-clone-skbs-for-each-listener.patch

Cleanup cpumask related code and rearrange functions for clarity

 include/linux/taskstats_kern.h |    5 ---
 kernel/taskstats.c             |   53 ++++++++++++++++++++++-------------------
 2 files changed, 29 insertions(+), 29 deletions(-)

Index: linux-2.6.18-rc1/include/linux/taskstats_kern.h
===================================================================
@@ -11,11 +11,6 @@
 #include <linux/sched.h>
 #include <net/genetlink.h>
 
-enum {
-	TASKSTATS_MSG_UNICAST,		/* send data only to requester */
-	TASKSTATS_MSG_MULTICAST,	/* send data to a group */
-};
-
 #ifdef CONFIG_TASKSTATS
 extern kmem_cache_t *taskstats_cache;
 extern struct mutex taskstats_exit_mutex;

Change documentation and example program to reflect the flow control issues being addressed by the cpumask changes.

 Documentation/accounting/getdelays.c   |  612 +++++++++++++++++----------------
 Documentation/accounting/taskstats.txt |   64 ++-
 2 files changed, 368 insertions(+), 308 deletions(-)

Index: linux-2.6.18-rc1/Documentation/accounting/taskstats.txt
===================================================================
@@ -26,20 +26,28 @@ leader - a process is deemed alive as lo
 Usage
 -----
 
-To get statistics during task's lifetime, userspace opens a unicast netlink
+To get statistics during a task's lifetime, userspace opens a unicast netlink
 socket (NETLINK_GENERIC family) and sends commands specifying a pid or a tgid.
 The response contains statistics for a task (if pid is specified) or the sum of
 statistics for all tasks of the process (if tgid is specified).
 
-To obtain statistics for tasks which are exiting, userspace opens a multicast
-netlink socket. Each time a task exits, its per-pid statistics is always sent
-by the kernel to each listener on the multicast socket. In addition, if it is
-the last thread exiting its thread group, an additional record containing the
-per-tgid stats are also sent. The latter contains the sum of per-pid stats for
-all threads in the thread group, both past and present.
+To obtain statistics for tasks which are exiting, the userspace listener
+sends a register command and specifies a cpumask. Whenever a task exits on
+one of the cpus in the cpumask, its per-pid statistics are sent to the
+registered listener. Using cpumasks allows the data received by one listener
+to be limited and assists in flow control over the netlink interface and is
+explained in more detail below.
+
+If the exiting task is the last thread exiting its thread group,
+an additional record containing the per-tgid stats is also sent to userspace.
+The latter contains the sum of per-pid stats for all threads in the thread
+group, both past and present.
 
 getdelays.c is a simple utility demonstrating usage of the taskstats interface
-for reporting delay accounting statistics.
+for reporting delay accounting statistics. Users can register cpumasks,
+send commands and process responses, listen for per-tid/tgid exit data,
+write the data received to a file and do basic flow control by increasing
+receive buffer sizes.
 
 Interface
 ---------

@@ -66,10 +74,20 @@ The messages are in the format
 
 The taskstats payload is one of the following three kinds:
 
-1. Commands: Sent from user to kernel. The payload is one attribute, of type
-TASKSTATS_CMD_ATTR_PID/TGID, containing a u32 pid or tgid in the attribute
-payload. The pid/tgid denotes the task/process for which userspace wants
-statistics.
+1. Commands: Sent from user to kernel. Commands to get data on
+a pid/tgid consist of one attribute, of type TASKSTATS_CMD_ATTR_PID/TGID,
+containing a u32 pid or tgid in the attribute payload. The pid/tgid denotes
+the task/process for which userspace wants statistics.
+
+Commands to register/deregister interest in exit data from a set of cpus
+consist of one attribute, of type
+TASKSTATS_CMD_ATTR_REGISTER/DEREGISTER_CPUMASK and contain a cpumask in the
+attribute payload. The cpumask is specified as an ascii string of
+comma-separated cpu ranges e.g. to listen to exit data from cpus 1,2,3,5,7,8
+the cpumask would be "1-3,5,7-8". If userspace forgets to deregister interest
+in cpus before closing the listening socket, the kernel cleans up its interest
+set over time. However, for the sake of efficiency, an explicit deregistration
+is advisable.
 
 2. Response for a command: sent from the kernel in response to a userspace
 command. The payload is a series of three attributes of type:

@@ -138,4 +156,26 @@ struct too much, requiring disparate use
 unnecessarily receive large structures whose fields are of no interest, then
 extending the attributes structure would be worthwhile.
 
+Flow control for taskstats
+--------------------------
+
+When the rate of task exits becomes large, a listener may not be able to keep
+up with the kernel's rate of sending per-tid/tgid exit data leading to data
+loss. This possibility gets compounded when the taskstats structure gets
+extended and the number of cpus grows large.
+
+To avoid losing statistics, userspace should do one or more of the following:
+
+- increase the receive buffer sizes for the netlink sockets opened by
+listeners to receive exit data.
+
+- create more listeners and reduce the number of cpus being listened to by
+each listener. In the extreme case, there could be one listener for each cpu.
+Users may also consider setting the cpu affinity of the listener to the subset
+of cpus to which it listens, especially if they are listening to just one cpu.
+
+Despite these measures, if the userspace receives ENOBUFS error messages
+indicated overflow of receive buffers, it should take measures to handle the
+loss of data.
+
 ----

Shift initialization of semaphores taken on exit() path to earlier in the bootup sequence. Without this fix, booting on large cpu machines hangs at down_read() called on one of the per-cpu semaphores declared in taskstats.

 kernel/taskstats.c |   12 ++++++------
 1 files changed, 6 insertions(+), 6 deletions(-)

Index: linux-2.6.18-rc1/kernel/taskstats.c
===================================================================
@@ -501,15 +501,20 @@ static struct genl_ops taskstats_ops = {
 /* Needed early in initialization */
 void __init taskstats_init_early(void)
 {
+	unsigned int i;
+
 	taskstats_cache = kmem_cache_create("taskstats_cache",
 						sizeof(struct taskstats),
 						0, SLAB_PANIC, NULL, NULL);
+	for_each_possible_cpu(i) {
+		INIT_LIST_HEAD(&(per_cpu(listener_array, i).list));
+		init_rwsem(&(per_cpu(listener_array, i).sem));
+	}
 }
 
 static int __init taskstats_init(void)
 {
 	int rc;
-	unsigned int i;
 
 	rc = genl_register_family(&family);
 	if (rc)

@@ -519,11 +524,6 @@ static int __init taskstats_init(void)
 	if (rc < 0)
 		goto err;
 
-	for_each_possible_cpu(i) {
-		INIT_LIST_HEAD(&(per_cpu(listener_array, i).list));
-		init_rwsem(&(per_cpu(listener_array, i).sem));
-	}
-
 	family_registered = 1;
 	return 0;
 err:

Remove listeners from per-cpu listener lists only if they've closed the socket (resulting in an ECONNREFUSED failure of genetlink unicast). For other errors returned by genlmsg_unicast like -EAGAIN which results from the receiver's buffer having insufficient space, userspace gets an ENOBUF warning and the kernel can continue.

 kernel/taskstats.c |    2 +-
 1 files changed, 1 insertion(+), 1 deletion(-)

Index: linux-2.6.18-rc1/kernel/taskstats.c
===================================================================
@@ -139,7 +139,7 @@ static int send_cpu_listeners(struct sk_
 	down_write(&listeners->sem);
 	list_for_each_entry_safe(s, tmp, &listeners->list, list) {
 		ret = genlmsg_unicast(skb, s->pid);
-		if (ret) {
+		if (ret == -ECONNREFUSED) {
 			list_del(&s->list);
 			kfree(s);
 			rc = ret;

Add another list utility function to check for last element in a list.

 include/linux/list.h |   11 +++++++++++
 1 files changed, 11 insertions(+)

Index: linux-2.6.18-rc1/include/linux/list.h
===================================================================
@@ -265,6 +265,17 @@ static inline void list_move_tail(struct
 }
 
 /**
+ * list_islast - tests whether @list is the last entry in list @head
+ * @list: the entry to test
+ * @head: the head of the list
+ */
+static inline int list_islast(const struct list_head *list,
+				const struct list_head *head)
+{
+	return list->next == head;
+}
+
+/**
  * list_empty - tests whether a list is empty
  * @head: the list to test.
  */

Use a cloned sk_buff for each netlink message sent to multiple listeners.

Earlier, the same skb, representing a netlink message, was being erroneously reused for doing genetlink_unicast()'s (effectively netlink_unicast()) to each listener on the per-cpu list of listeners. Since netlink_unicast() frees up the skb passed to it, regardless of status of the send, reuse is bad.

Thanks to Chandra Seetharaman for discovering this bug.

 kernel/taskstats.c |   13 ++++++++++++-
 1 files changed, 12 insertions(+), 1 deletion(-)

Index: linux-2.6.18-rc1/kernel/taskstats.c
===================================================================
@@ -125,6 +125,7 @@ static int send_cpu_listeners(struct sk_
 	struct genlmsghdr *genlhdr = nlmsg_data((struct nlmsghdr *)skb->data);
 	struct listener_list *listeners;
 	struct listener *s, *tmp;
+	struct sk_buff *skb_next, *skb_cur = skb;
 	void *reply = genlmsg_data(genlhdr);
 	int rc, ret;
 

@@ -138,12 +139,22 @@ static int send_cpu_listeners(struct sk_
 	listeners = &per_cpu(listener_array, cpu);
 	down_write(&listeners->sem);
 	list_for_each_entry_safe(s, tmp, &listeners->list, list) {
-		ret = genlmsg_unicast(skb, s->pid);
+		skb_next = NULL;
+		if (!list_islast(&s->list, &listeners->list)) {
+			skb_next = skb_clone(skb_cur, GFP_KERNEL);
+			if (!skb_next) {
+				nlmsg_free(skb_cur);
+				rc = -ENOMEM;
+				break;
+			}
+		}
+		ret = genlmsg_unicast(skb_cur, s->pid);
 		if (ret == -ECONNREFUSED) {
 			list_del(&s->list);
 			kfree(s);
 			rc = ret;
 		}
+		skb_cur = skb_next;
 	}
 	up_write(&listeners->sem);
 

We do GFP_KERNEL inside semaphores/mutexes in lots of places. So if this can deadlock with the oom-killer we probably should fix that, preferably by having GFP_KERNEL fail in that case.

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

This lock is special, in that it's taken on the exit() path (I think). So it can block tasks which are trying to exit.

But yes. Reliable, deadlock-free oom-killing is, err, a matter of ongoing research.

Sorry, missed the context.

If there is a deadlock then it's not just this allocation that you need worry about. There is also an allocation within genlmsg_uniast that would be GFP_KERNEL.

Cheers,

Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Hmm...doesn't look very safe does it.
There's no real need for us to skb_clone within the sem. Keeping a count of listeners and doing the clone outside should let us avoid this problem.

I was trying to avoid doing the above because of the potential for listeners getting added continuously to the list
(and having to repeat the allocation loop outside the down_write).

But on second thoughts, we're under no obligation to send the data to all the listeners who add themselves in the short time between our taking a snapshot of the listener count and when the send is done (within the down_write). So it should be ok.

Thats true. The GFP_KERNEL allocation potentially called in netlink_trim() as part of the genlmsg/netlink_unicast() is again a problem.

So perhaps we should switch to using RCU for protecting the listener list.

--Shailabh

Remove down_write() from taskstats code invoked on the exit() path.

In send_cpu_listeners(), which is called on the exit path, a down_write() was protecting operations like skb_clone() and genlmsg_unicast() that do GFP_KERNEL allocations. If the oom-killer decides to kill tasks to satisfy the allocations,the exit of those tasks could block on the same semphore.

The down_write() was only needed to allow removal of invalid listeners from the listener list. The patch converts the down_write to a down_read and defers the removal to a separate critical region. This ensures that even if the oom-killer is called, no other task's exit is blocked as it can still acquire another down_read.

Thanks to Andrew Morton & Herbert Xu for pointing out the oom related pitfalls, and to Chandra Seetharaman for suggesting this fix instead of using something more complex like RCU.

---

 kernel/taskstats.c |   24 +++++++++++++++++++-----
 1 files changed, 19 insertions(+), 5 deletions(-)

Index: linux-2.6.18-rc1/kernel/taskstats.c
===================================================================
@@ -51,6 +51,7 @@ __read_mostly = {
 struct listener {
 	struct list_head list;
 	pid_t pid;
+	char valid;
 };
 
 struct listener_list {

@@ -127,7 +128,7 @@ static int send_cpu_listeners(struct sk_
 	struct listener *s, *tmp;
 	struct sk_buff *skb_next, *skb_cur = skb;
 	void *reply = genlmsg_data(genlhdr);
-	int rc, ret;
+	int rc, ret, delcount = 0;
 
 	rc = genlmsg_end(skb, reply);
 	if (rc < 0) {

@@ -137,7 +138,7 @@ static int send_cpu_listeners(struct sk_
 
 	rc = 0;
 	listeners = &per_cpu(listener_array, cpu);
-	down_write(&listeners->sem);
+	down_read(&listeners->sem);
 	list_for_each_entry_safe(s, tmp, &listeners->list, list) {
 		skb_next = NULL;
 		if (!list_islast(&s->list, &listeners->list)) {

@@ -150,14 +151,26 @@ static int send_cpu_listeners(struct sk_
 		}
 		ret = genlmsg_unicast(skb_cur, s->pid);
 		if (ret == -ECONNREFUSED) {
-			list_del(&s->list);
-			kfree(s);
+			s->valid = 0;
+			delcount++;
 			rc = ret;
 		}
 		skb_cur = skb_next;
 	}
-	up_write(&listeners->sem);
+	up_read(&listeners->sem);
+
+	if (!delcount)
+		return rc;
 
+	/* Delete invalidated entries */
+	down_write(&listeners->sem);
+	list_for_each_entry_safe(s, tmp, &listeners->list, list) {
+		if (!s->valid) {
+			list_del(&s->list);
+			kfree(s);
+		}
+	}
+	up_write(&listeners->sem);
 	return rc;
 }
 

@@ -290,6 +303,7 @@ static int add_del_listener(pid_t pid, c
 				goto cleanup;
 			s->pid = pid;
 			INIT_LIST_HEAD(&s->list);
+			s->valid = 1;
 
 			listeners = &per_cpu(listener_array, cpu);
 			down_write(&listeners->sem);

To illustrate the basic premise behind the cpumask changes namely, reducing the number of cpus results in fewer overflow conditions, Chandra ran the following experiment on an 8-way PIII box:

- "mkthreads 1000 1000" (the program which only forks/exits) with minimum time spent inside the thread function. This is basically an exit rate that is higher than the 1000/cpu/sec discussed earlier.

- A slightly modified version of the getdelays.c example that is included in patch 2/6 in this series of postings. Modification was to print only the number of receives and number of ENOBUFS seen.

The -m parameter specifies the cpumask,
-r parameter is the size of the socket receive buffer -l results in listening for exit data

The following sets of runs are self-explanatory. Initial run emulates the earlier behaviour where one listener receives data for all cpus. As the number of cpus to which it listens is reduced, the ENOBUFS reduce.

Similarly, increasing the receive buffer size also cuts down on the ENOBUFS, further helped by reducing number of cpus listened to. The final data point, not shown here, is when the receive buffer size is set to some high number like 8K when the ENOBUFS aren't seen at all.

===================================

Each output shows
stats <number of msgs rcvd> enobufs <num of enobufs seen> cumulatively

elm3b94:/tmp # ./getdelays -m 0-7 -r 512 -l
cpumask 0-7 maskset 1
receive buf size 512
listen forever
stats 100000, enobufs 2540
stats 200000, enobufs 5701
stats 300000, enobufs 8482
stats 400000, enobufs 11332
stats 500000, enobufs 14256
stats 600000, enobufs 17150
stats 700000, enobufs 19981
stats 800000, enobufs 22971
stats 900000, enobufs 26324
stats 1000000, enobufs 29291

elm3b94:/tmp # ./getdelays -m 0-3 -r 512 -l
cpumask 0-3 maskset 1
receive buf size 512
listen forever
stats 100000, enobufs 831
stats 200000, enobufs 1772
stats 300000, enobufs 2728
stats 400000, enobufs 3820
stats 500000, enobufs 5030
stats 600000, enobufs 6501
stats 700000, enobufs 7885
stats 800000, enobufs 8971
stats 900000, enobufs 10262
stats 1000000, enobufs 11786

elm3b94:/tmp # ./getdelays -m 2-3 -r 512 -l
cpumask 2-3 maskset 1
receive buf size 512
listen forever
stats 100000, enobufs 106
stats 200000, enobufs 206
stats 300000, enobufs 313
stats 400000, enobufs 389
stats 500000, enobufs 477
stats 600000, enobufs 676
stats 700000, enobufs 860
stats 800000, enobufs 1048
stats 900000, enobufs 1189
stats 1000000, enobufs 1303

elm3b94:/tmp # ./getdelays -m 0 -r 512 -l
cpumask 0 maskset 1
receive buf size 512
listen forever
stats 100000, enobufs 100
stats 200000, enobufs 162
stats 300000, enobufs 302
stats 400000, enobufs 399
stats 500000, enobufs 507
stats 600000, enobufs 571
stats 700000, enobufs 666
stats 800000, enobufs 725
stats 900000, enobufs 821
stats 1000000, enobufs 909

================= with recv buf size 2048

elm3b94:/tmp # ./getdelays -m 0-7 -r 2048 -l
cpumask 0-7 maskset 1
receive buf size 2048
listen forever
stats 100000, enobufs 35
stats 200000, enobufs 88
stats 300000, enobufs 123
stats 400000, enobufs 138
stats 500000, enobufs 155
stats 600000, enobufs 191
stats 700000, enobufs 223
stats 800000, enobufs 238
stats 900000, enobufs 280
stats 1000000, enobufs 319

elm3b94:/tmp # ./getdelays -m 4-7 -r 2048 -l
cpumask 4-7 maskset 1
receive buf size 2048
listen forever
stats 100000, enobufs 10
stats 200000, enobufs 17
stats 300000, enobufs 28
stats 400000, enobufs 35
stats 500000, enobufs 49
stats 600000, enobufs 63
stats 700000, enobufs 80
stats 800000, enobufs 94
stats 900000, enobufs 114
stats 1000000, enobufs 138

elm3b94:/tmp # ./getdelays -m 2-3 -r 2048 -l
cpumask 2-3 maskset 1
receive buf size 2048
listen forever
stats 100000, enobufs 5
stats 200000, enobufs 6
stats 300000, enobufs 10
stats 400000, enobufs 14
stats 500000, enobufs 19
stats 600000, enobufs 33
stats 700000, enobufs 38
stats 800000, enobufs 43
stats 900000, enobufs 54
stats 1000000, enobufs 59

elm3b94:/tmp # ./getdelays -m 1 -r 2048 -l
cpumask 1 maskset 1
receive buf size 2048
listen forever
stats 100000, enobufs 3
stats 200000, enobufs 6
stats 300000, enobufs 19
stats 400000, enobufs 25
stats 500000, enobufs 30
stats 600000, enobufs 31
stats 700000, enobufs 33
stats 800000, enobufs 45
stats 900000, enobufs 48
stats 1000000, enobufs 52

Btw, did you ever explain what this delay accounting code is useful for exactly? It's an awfull lot of code that doesn't seem to have a huge use. While we're at it do you have a pointer to the associated userspace code?

Yes.
Previous postings have explained the rationale,

http://www.uwsg.indiana.edu/hypermail/linux/kernel/0511.1/2275.html
http://www.uwsg.indiana.edu/hypermail/linux/kernel/0512.0/2152.html

lwn.net had a good summary as always,
http://lwn.net/Articles/173209/

The delay accounting part of the code is quite small (just a few lines of timestamping code place in core kernel code) and much of the remaining size comes from the interface. Since the interface is designed to be of generic use towards ANY per-task accounting needs, discussions and code have been fairly involved. We went through a long discussion of potential exploiters:

(see thread under [Patch 0/8] per-task delay accounting at
http://www.uwsg.indiana.edu/hypermail/linux/kernel/0603.3/index.html

Its part of the patches in Documentation/accounting/getdelays.c

and the last-but-one version of it can be viewed at its location in the -mm tree:
http://www.linux-m32r.org/lxr/http/source/Documentation/accounting/?a=generic

(The just accepted patches updates the documentation especially the parts relating to cpumasks but the above should also suffice to give a flavor of what userspace could do).

Thanks,
Shailabh