nproc: netlink access to /proc information

[ Cc: contributors to recent, related thread ]

nproc is an attempt to address the current problems with /proc. In short, it exposes the same information via netlink (implemented for a small subset).

This patch is experimental. I'm posting it to get the discussion going.

Problems with /proc
===================
The information in /proc comes in a number of different formats, for example:

- /proc/PID/stat works for parsers. However, because it is not self-documenting, it can never shrink, It contains a growing number of dead fields -- legacy tools expect them to be there. To make things worse, there is no N/A value, which makes a field value 0 ambiguous.

- /proc/pid/status is self-documenting. No N/A value is necessary -- fields can easily be added, removed, and reordered. Too easily, maybe. Tool maintainers complain about parsing overhead and unstable file formats.

- /proc/slabinfo is something of a hybrid and tries to avoid the weaknesses of other formats.

So a key problem is that it's hard to make an interface that is both easy for humans and parsers to read. The amount of human-readable information in /proc has been growing and there's no way all these files will be rewritten again to favor parsers.

Another problem with /proc is speed. If we put all information in a few large files, the kernel needs to calculate many fields even if a tool is only interested in one of them. OTOH, if the informations is split into many small files, VFS and related overhead increases if a tool needs to read many files just for the information on one single process.

In summary, /proc suffers from diverging goals of its two groups of users (human readers and parsers), and it doesn't scale well for tools monitoring many fields or many processes.

Overview
========
This patch implements an alternative method of querying the kernel with well-defined messages through netlink.

Each piece of information ("field") like MemFree or VmRSS is given a 32 bit ID:

bits
0-15 a unique ID
16-23 reserved
24-27 data type (u32, unsigned long, u64, string)
28-31 the scope (process, global)

Four operations exist to query the kernel:

NPROC_GET_LIST
--------------
This request has no payload. The kernel answers with a sequence of u32 values. The first one announces the number of fields known to the kernel, the rest of the message lists all of them by IDs.

NPROC_GET_LIST allows a tools to check which fields are still available and -- if the tool author is so inclined -- to discover new fields dynamically.

NPROC_GET_LABEL
---------------
A label request contains a u32 value indicating the type of label and one key for which a label is wanted. The kernel returns a string containing the label. Label types are field (useful for dynamically discovered fields) and ksym.

NPROC_GET_GLOBAL
----------------
A request for one or more fields with a global scope (e.g. MemFree, nr_dirty) contains a u32 value announcing the number of requested fields and a matching sequence of fields IDs.

The kernel replies with one netlink message containing the requested fields. A string field is lead by a u32 value indicating the remaining length of the field. I didn't want to offer any strings outside of the label operation initially, but having to make an extra call for, say, every process name seemed a bit excessive.

NPROC_SCOPE_PROCESS
-------------------
For fields with a process scope (e.g. VmSize, wchan), a request starts as above. It adds an additional part, though: The selector. The only selector implemented so far takes a list of u32 PID values.

At the moment, the kernel sends a separate netlink message for every process.

Results
=======
- The new interface is self-documenting.

- There is no need to ever parse strings on either side of the user/kernel space barrier.

- Fields that have become meaningless or are unmaintained are simply removed. Tools can easily detect if fields (and which ones) are missing. (Of course that does not imply that any field is fair game to remove from the kernel.)

- Any number and combination of fields can be gathered with one single message exchange (as long as they are in the same scope).

- The kernel only calculates fields as requested (where it makes sense, see __task_mem for an example).

- The conflict between human-readable and machine-parsable files is solved by providing an interface each.

- While parsing answers is vastly easier for tools, there hardly any additional complexity in the kernel (except for the process selector which is optional as it goes beyond the functionality offered by /proc).

- If we're lucky, we may even be able to save memory on small systems that want to do away with /proc but need access to some of the information it provides.

I haven't implemented any form of access control. One possibility is to use some of the reserved bits in the ID field to indicate access restrictions to both kernel and user space (e.g. everyone, process owner, root) and add some LSM hook for those needing fine-grained control.

It would also be easy to add semantics that won't work in /proc (for instance a simple mechanism for repetitive requests -- just add an optional frequency or interval flag). Whether that is desirable or not is a separate discussion, though.

There are obvious speed optimizations I haven't tried. I meant to conduct some performance tests, but I'm not sure what a meaningful benchmark on the /proc file side is. Suggestions?

Roger

The current code duplicates some data gathering logic from elsewhere in the kernel. The code can be trivially shared if the exisiting users in proc split data gathering and string creation.

The patch should apply against any current 2.6 kernel.

 include/linux/netlink.h |    1 
 include/linux/nproc.h   |   93 ++++++
 init/Kconfig            |    7 
 kernel/Makefile         |    1 
 kernel/nproc.c          |  690 ++++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 792 insertions(+)

diff -uNp -X /home/rl/data/doc/kernel/dontdiff-2.6 linux-2.6.8/include/linux/netlink.h linux-2.6.8-nproc/include/linux/netlink.h
@@ -15,6 +15,7 @@
 #define NETLINK_ARPD		8
 #define NETLINK_AUDIT		9	/* auditing */
 #define NETLINK_ROUTE6		11	/* af_inet6 route comm channel */
+#define NETLINK_NPROC		12	/* /proc information */
 #define NETLINK_IP6_FW		13
 #define NETLINK_DNRTMSG		14	/* DECnet routing messages */
 #define NETLINK_TAPBASE		16	/* 16 to 31 are ethertap */

diff -uNp -X /home/rl/data/doc/kernel/dontdiff-2.6 linux-2.6.8/kernel/Makefile linux-2.6.8-nproc/kernel/Makefile
@@ -15,6 +15,7 @@ obj-$(CONFIG_SMP) += cpu.o
 obj-$(CONFIG_UID16) += uid16.o
 obj-$(CONFIG_MODULES) += module.o
 obj-$(CONFIG_KALLSYMS) += kallsyms.o
+obj-$(CONFIG_NPROC) += nproc.o
 obj-$(CONFIG_PM) += power/
 obj-$(CONFIG_BSD_PROCESS_ACCT) += acct.o
 obj-$(CONFIG_COMPAT) += compat.o

diff -uNp -X /home/rl/data/doc/kernel/dontdiff-2.6 linux-2.6.8/init/Kconfig linux-2.6.8-nproc/init/Kconfig
@@ -141,6 +141,13 @@ config SYSCTL
 	  building a kernel for install/rescue disks or your system is very
 	  limited in memory.
 
+config NPROC
+	bool "Netlink interface to /proc information"
+	depends on PROC_FS && EXPERIMENTAL
+	default y
+	help
+	  Nproc is a netlink interface to /proc information.
+
 config AUDIT
 	bool "Auditing support"
 	default y if SECURITY_SELINUX

I failed to mention that the patch is missing some rather basic locking (say, in nproc_select_pid). Yeah, it is _that_ experimental :-/. I ignored the locking issue when mulling over the semantics of the new interface and forgot it later.

The patch below should be an improvement.

Roger

@@ -278,18 +278,23 @@ int nproc_select_pid(struct nlmsghdr *nl
 
 	for (i = 0; i < tcnt; i++) {
 		task_t *tsk;
+		read_lock(&tasklist_lock);
 		tsk = find_task_by_pid(pids[i]);
+		if (tsk)
+			get_task_struct(tsk);
+		read_unlock(&tasklist_lock);
+		if (!tsk)
+			goto err_srch;
 		pdebug("task found for pid %d: %s.\n", pids[i], tsk->comm);
-		if (!tsk) {
-			err = -ESRCH;
-			goto out;
-		}
 		err = nproc_pid_fields(nlh, fdata, len, tsk);
+		put_task_struct(tsk);
 	}
 
-out:
 	return err;
 
+err_srch:
+	return -ESRCH;
+
 err_inval:
 	return -EINVAL;
 }

On a system running a kernel with nproc, the sample program (below) spits out the information it can gather from the kernel: Available fields, data types, and associated values.

Obviously, real tools would have their own labels (and help texts) for well-known fields. Scope information and the NPROC_GET_LABEL operation allow them to provide additional information in a meaningful context.

The sample program does have some extra knowledge beyond the bare
interface: It knows that a time stamp (global scope) can be requested within process scope as well, and it knows how to request a symbol name from a wchan value.

Sample output:
----------------------------------------------------------------------------
================ Available fields =======================

    ----id---- --------label------- -scope- ----type-----
# 0 0x22000001 PID                  process __u32
# 1 0x21000002 Name                 process string
# 2 0x12000004 MemFree              global  __u32
# 3 0x12000005 PageSize             global  __u32
# 4 0x14000006 Jiffies              global  __u64
# 5 0x22000010 VmSize               process __u32
# 6 0x22000011 VmLock               process __u32
# 7 0x22000012 VmRSS                process __u32
# 8 0x22000013 VmData               process __u32
# 9 0x22000014 VmStack              process __u32
#10 0x22000015 VmExe                process __u32
#11 0x22000016 VmLib                process __u32
#12 0x13000051 nr_dirty             global  unsigned long
#13 0x13000052 nr_writeback         global  unsigned long
#14 0x13000053 nr_unstable          global  unsigned long
#15 0x13000054 nr_page_table_pages  global  unsigned long
#16 0x13000055 nr_mapped            global  unsigned long
#17 0x13000056 nr_slab              global  unsigned long
#18 0x23000100 wchan                process unsigned long
#19 0x01000101 wchan_symbol         (    0) string

================ Global fields ==========================

    ----id---- --------label------- --value---

# 0 0x12000004 MemFree 97926
# 1 0x12000005 PageSize 4096
# 2 0x14000006 Jiffies 4298132669
# 3 0x13000051 nr_dirty 10
# 4 0x13000052 nr_writeback 0
# 5 0x13000053 nr_unstable 0
# 6 0x13000054 nr_page_table_pages 405
# 7 0x13000055 nr_mapped 36021
# 8 0x13000056 nr_slab 5956

================ Process fields ========================= ---------------- process PID 14318 ----------------------

    ----id---- --------label------- --value---

# 0 0x14000006 Jiffies 4298132669
# 1 0x22000001 PID 14318
# 2 0x21000002 Name tst
# 3 0x22000010 VmSize 1456
# 4 0x22000011 VmLock 0
# 5 0x22000012 VmRSS 360
# 6 0x22000013 VmData 272
# 7 0x22000014 VmStack 12
# 8 0x22000015 VmExe 8
# 9 0x22000016 VmLib 1140
#10 0x23000100 wchan 0
---------------- process PID 1 ----------------------

    ----id---- --------label------- --value---

# 0 0x14000006 Jiffies 4298132669
# 1 0x22000001 PID 1
# 2 0x21000002 Name init
# 3 0x22000010 VmSize 1340
# 4 0x22000011 VmLock 0
# 5 0x22000012 VmRSS 468
# 6 0x22000013 VmData 144
# 7 0x22000014 VmStack 4
# 8 0x22000015 VmExe 28
# 9 0x22000016 VmLib 1140
#10 0x23000100 wchan 0xc01924f9 (ksym: do_select)

1000 iterations for both processes:

	CPU time : 0.000000s
	Wall time: 0.008305s

============================================================================
Sample code below:
----------------------------------------------------------------------------
#include <asm/types.h>
#include <sys/socket.h>
#include <linux/netlink.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include <time.h>
#include <sys/time.h>

/* Sample code to demonstrate nproc usage */

//#include "<linux/nproc.h>"

#define NPROC_BASE 0x10
#define NPROC_GET_LIST (NPROC_BASE+0)
#define NPROC_GET_LABEL (NPROC_BASE+1)
#define NPROC_GET_GLOBAL (NPROC_BASE+2)
#define NPROC_GET_PS (NPROC_BASE+3)

#define NETLINK_NPROC 12

#define NPROC_SCOPE_MASK 0xF0000000
#define NPROC_SCOPE_GLOBAL 0x10000000 /* Global w/o arguments */
#define NPROC_SCOPE_PROCESS 0x20000000
#define NPROC_SCOPE_LABEL 0x30000000

#define NPROC_TYPE_MASK 0x0F000000
#define NPROC_TYPE_STRING 0x01000000
#define NPROC_TYPE_U32 0x02000000
#define NPROC_TYPE_UL 0x03000000
#define NPROC_TYPE_U64 0x04000000

#define NPROC_SELECT_ALL 0x00000001
#define NPROC_SELECT_PID 0x00000002
#define NPROC_SELECT_UID 0x00000003

#define NPROC_LABEL_FIELD 0x00000001
#define NPROC_LABEL_KSYM 0x00000002

struct nproc_field {
	__u32	id;
	const char *label;
};

#define NPROC_JIFFIES (0x00000006 | NPROC_TYPE_U64 | NPROC_SCOPE_GLOBAL)
#define NPROC_WCHAN (0x00000100 | NPROC_TYPE_UL | NPROC_SCOPE_PROCESS)

//#define DEBUG

#ifdef DEBUG
#define pdebug(x,args...) printf("%s:%d " x, __func__ , __LINE__, ##args) #else
#define pdebug(x,args...)
#endif
#define perror(x,args...) fprintf(stderr, "%s:%d " x, __func__ , __LINE__, ##args)

static __u32 seq_nr;
static pid_t pid;
static int nsk; /* netlink socket */

struct proc_message {
	struct nlmsghdr nlh;
	__u32 data[256];
};

int open_netlink()

{
	if ((nsk = socket(PF_NETLINK, SOCK_RAW, NETLINK_NPROC)) == -1) {
		perror("Failed to open netlink proc socket.\n");
		exit(1);
	}
	return nsk;
}

void send_request(struct proc_message *req)

{
	int sent;

	req->nlh.nlmsg_flags = NLM_F_REQUEST;
	req->nlh.nlmsg_seq = seq_nr++;
	req->nlh.nlmsg_pid = pid;

	if ((sent = send(nsk, req, req->nlh.nlmsg_len, 0)) == -1) {
		perror("Failed to send netlink proc msg.\n");
		exit(1);
	}
		pdebug("sent %d bytes seq %#x type %#x \n", sent,
				req->nlh.nlmsg_seq, req->nlh.nlmsg_type);
}

void *get_reply(__u32 type, struct proc_message *ans)

{
	int len;
	if ((len = recv(nsk, ans, sizeof(struct proc_message), 0)) == -1) {
		perror("Failed to read netlink proc msg.\n");
		exit(1);
	};

	if (!NLMSG_OK((&(*ans).nlh), len)) {
		perror("Bad netlink msg.\n");
		exit(1);
	}

	if (ans->nlh.nlmsg_type != type) {
		perror("read %d bytes seq %#x type %#x len %d\n", len,
				ans->nlh.nlmsg_seq, ans->nlh.nlmsg_type,
				ans->nlh.nlmsg_len);
		exit(1);
	}
	else
		pdebug("read %d bytes seq %#x type %#x len %d\n", len,
				ans->nlh.nlmsg_seq, ans->nlh.nlmsg_type,
				ans->nlh.nlmsg_len);

	return NLMSG_DATA(&ans->nlh);
}

void *get_global(__u32 num, struct proc_message *nlmsg)

{
	int len = num * sizeof(__u32);

	nlmsg->nlh.nlmsg_len = NLMSG_LENGTH(len);
	nlmsg->nlh.nlmsg_type = NPROC_GET_GLOBAL;

	send_request(nlmsg);

	return get_reply(NPROC_GET_GLOBAL, nlmsg);
}

void get_ps(__u32 num, struct proc_message *nlmsg)

{
	int len = num * sizeof(__u32);

	nlmsg->nlh.nlmsg_len = NLMSG_LENGTH(len);
	nlmsg->nlh.nlmsg_type = NPROC_GET_PS;

	send_request(nlmsg);
}

char *get_label(struct proc_message *nlmsg)

{
	nlmsg->nlh.nlmsg_type = NPROC_GET_LABEL;

	send_request(nlmsg);

	return get_reply(NPROC_GET_LABEL, nlmsg);
}

char *get_field_label(__u32 id, struct proc_message *nlmsg)

{
	__u32 *buf = NLMSG_DATA(&nlmsg->nlh);
	int len = 2 * sizeof(__u32);

	nlmsg->nlh.nlmsg_len = NLMSG_LENGTH(len);

	buf[0] = NPROC_LABEL_FIELD;
	buf[1] = id;

	return get_label(nlmsg);
}

char *get_ksym(unsigned long wchan, struct proc_message *nlmsg)

{
	__u32 *buf = NLMSG_DATA(&nlmsg->nlh);
	unsigned long *addr;
	int len = sizeof(__u32) + sizeof(unsigned long);

	*buf++ = NPROC_LABEL_KSYM;
	addr = (unsigned long *)buf;
	*addr = wchan;

	nlmsg->nlh.nlmsg_len = NLMSG_LENGTH(len);

	return get_label(nlmsg);
}

__u32 *get_list(struct proc_message *nlmsg)

{
	nlmsg->nlh.nlmsg_len = NLMSG_LENGTH(0);
	nlmsg->nlh.nlmsg_type = NPROC_GET_LIST;

	send_request(nlmsg);

	return get_reply(NPROC_GET_LIST, nlmsg);
}

void print_ps(char *res, int psc, struct nproc_field *ps_label)

{
	int i;
	struct proc_message nlmsg;

	printf("    ----id---- --------label------- --value---\n");
	for (i = 0; i < psc; i++) {
		const char *label = ps_label[i].label;
		__u32 id    = ps_label[i].id;
		__u32 type  = id & NPROC_TYPE_MASK;

		printf("#%2d %#x %-20s ", i, id, label);
		switch (type) {
			case NPROC_TYPE_U32: {
				__u32 *p = (__u32 *)res;
				printf("%10u\n", *p);
				res = (char *)++p;
				break;
			}
			case NPROC_TYPE_UL: {
				unsigned long *p = (unsigned long *)res;
				if ((id == NPROC_WCHAN) && *p) {
					printf("%#8lx ", *p);
					printf("(ksym: %s)\n", get_ksym(*p,
								&nlmsg));
				}
				else
					printf("%10lu\n", *p);
				res = (char *)++p;
				break;
			}
			case NPROC_TYPE_U64: {
				__u64 *p = (__u64 *)res;
				printf("%10llu\n", *p);
				res = (char *)++p;
				break;
			}
			case NPROC_TYPE_STRING: {
				__u32 *len = (__u32 *)res;
				char *p = res + sizeof(__u32);
				printf("%s\n", p);
				res += *len + sizeof(__u32);
				break;
			}
			default:
				printf("(?)\t");
		}
	}
}

#define MAX_FIELDS 64

int main() {
	struct proc_message flist;
	struct proc_message nlmsg;
	struct proc_message gl_msg;
	struct proc_message ps_msg;

	__u32 *fields;
	__u32 *gl = NLMSG_DATA(&gl_msg.nlh);
	__u32 *ps = NLMSG_DATA(&ps_msg.nlh);

	struct nproc_field gl_label[MAX_FIELDS];
	struct nproc_field ps_label[MAX_FIELDS];

	char *res;

	int i;
	int ac, glc = 0, psc = 0;		/* Count fields */

	int cpu_0;
	struct timeval tv0, tv1;
	float wall;
	struct timezone tz;

	pid = getpid();
	nsk = open_netlink();

	fields = get_list(&flist);
	ac = *fields++;


	*gl++ = 0;		/* Reserve space for field count */
	*ps++ = 0;

	*ps++ = NPROC_JIFFIES;	/* Special: both global and ps context */
	ps_label[psc].id = NPROC_JIFFIES;
	ps_label[psc++].label = strdup(get_field_label(NPROC_JIFFIES, &nlmsg));

	printf("================ Available fields =======================\n");
	printf("    ----id---- --------label------- -scope- ----type-----\n");
	for (i = 0; i < ac; i++) {
		char *label;
		__u32 scope, type;

		scope = fields[i] & NPROC_SCOPE_MASK;
		type  = fields[i] & NPROC_TYPE_MASK;
		label = strdup(get_field_label(fields[i], &nlmsg));

		printf("#%2d %#8.8x %-20s ", i, fields[i], label);
		switch (scope) {
			case NPROC_SCOPE_GLOBAL:
				printf("global  ");
				*gl++ = fields[i];
				gl_label[glc].id = fields[i];
				gl_label[glc++].label = label;
				break;
			case NPROC_SCOPE_PROCESS:
				printf("process ");
				*ps++ = fields[i];
				ps_label[psc].id = fields[i];
				ps_label[psc++].label = label;
				break;
			default:
				printf("(%#5x) ", scope);
		}
		switch (type) {
			case NPROC_TYPE_U32:
				printf("__u32");
				break;
			case NPROC_TYPE_UL:
				printf("unsigned long");
				break;
			case NPROC_TYPE_U64:
				printf("__u64");
				break;
			case NPROC_TYPE_STRING:
				printf("string");
				break;
			default:
				printf("type: (%#8.8x)\t", type);
		}
		if ((glc == MAX_FIELDS) || (psc == MAX_FIELDS)) {
			perror("Array too small.\n");
			exit(1);
		}
		printf("\n");
	}

	gl = NLMSG_DATA(&gl_msg.nlh);
	*gl = glc;

	res = get_global(glc + 1, &gl_msg);

	printf("\n================ Global fields ==========================\n");
	printf("    ----id---- --------label------- --value---\n");
	for (i = 0; i < glc; i++) {
		const char *label = gl_label[i].label;
		__u32 id    = gl_label[i].id;
		__u32 type  = id & NPROC_TYPE_MASK;

		printf("#%2d %#8.8x %-20s ", i, id, label);
		switch (type) {
			case NPROC_TYPE_U32: {
				__u32 *p = (__u32 *)res;
				printf("%10u", *p);
				res = (char *)++p;
				break;
			}
			case NPROC_TYPE_UL: {
				unsigned long *p = (unsigned long *)res;
				printf("%10lu", *p);
				res = (char *)++p;
				break;
			}
			case NPROC_TYPE_U64: {
				__u64 *p = (__u64 *)res;
				printf("%10llu", *p);
				res = (char *)++p;
				break;
			}
			case NPROC_TYPE_STRING: {
				__u32 *len = (__u32 *)res;
				char *p = res + sizeof(__u32);
				printf("%s", p);
				res += *len + sizeof(__u32);
				break;
			}
			default:
				printf("(?)");
		}
		printf("\n");
	}

	printf("\n================ Process fields =========================\n");

	*ps++ = NPROC_SELECT_PID;
	*ps++ = 2;		// Number of PIDs to follow
	*ps++ = pid;
	*ps++ = 1;

	ps = NLMSG_DATA(&ps_msg.nlh);
	*ps = psc;

	get_ps(psc + 1 + 4, &ps_msg);

	res = get_reply(NPROC_GET_PS, &nlmsg);

	printf("---------------- process PID %5d ----------------------\n", pid);
	print_ps(res, psc, ps_label);

	res = get_reply(NPROC_GET_PS, &nlmsg);
	printf("---------------- process PID %5d ----------------------\n", 1);
	print_ps(res, psc, ps_label);

	gettimeofday(&tv0, &tz);
	cpu_0 = clock();

#define RUNS 1000
	for (i = 0; i < RUNS; i++) {
		get_ps(psc + 1 + 4, &ps_msg);
		get_reply(NPROC_GET_PS, &nlmsg);
		get_reply(NPROC_GET_PS, &nlmsg);
	}

	printf("\n%d iterations for both processes:\n", RUNS);
	printf("\tCPU time : %fs\n", (float)(clock() - cpu_0)/CLOCKS_PER_SEC);
	gettimeofday(&tv1,&tz);
	wall = (float) tv1.tv_sec - tv0.tv_sec +
		(tv1.tv_usec - tv0.tv_usec) / 1.0e6;
	printf("\tWall time: %fs\n", wall);

	return 0;
}

----------------------------------------------------------------------------

You should look at the way rtnetlink dumps large amounts of data to userspace.

So, user tools would all need to be privileged? That sounds problematic.

Control over the user request, or what the kernel returns? If the latter, LSM is not really a filtering API.

- James

James Morris
<[email protected]>

At this point, I am just using a working prototype to gauge the interest in an improved interface. Other than that, I agree. This would be one of the "speed optimizations I haven't tried".

It just means that not all the pieces that would be required to make this a merge candidate have been implemented. I focused on the basic infrastructure that is needed for the basic protocol.

Adding some access control that is about as smart as file permissions in /proc is fairly easy (we have the caller pid and netlink_skb_parms as a starting point). We only have read permissions to care about. It's trivial to flag each field as "world readable", "owner only" (for fields with process scope), and "root only". That covers pretty much what /proc permissions achieve. While I am confident that this will work, others may have better ideas for access control.

Roger

These are many of the same issues raised in rusty's "current /proc/ of shit" thread from a while back.

There are more maintainability benefits from the interface improvement than speed benefits. How many processes did you microbenchmark with? I see no evidence that this will be a speedup with large numbers of processes, as the problematic algorithms are preserved wholesale.

-- wli

Well, as far as THAT goes, I thought your tree-based lookup was nice. I assume you still have the code.

What we got instead was a sort of cached directory offset computation, which looks great... until you hit the bad case. I suggest that the people trying to reduce latency should try "top -d 0 -b >> /dev/null" while running something like the SDET benchmark.

I can resurrect that easily enough.

-- wli

The problems are not new. The driver stuff has been outsourced to /sysfs in the meantime, though, and the information that is being added to /proc these days is usually human-readable and a pain to parse.

Agreed. That has been my initial motivation. Speed is a bonus.

Nothing worth mentioning. I have nothing in /proc space to compare to. I was hoping someone would suggest a /proc based benchmark.

It doesn't fundamentally change the complexity, but I expect the reduction in overhead to be noticeable, mostly due to:
- no more string parsing.
- fewer system calls.
- fewer cycles wasted on calculating unnecessary data fields.

Roger

After some closer review it appears recent algorithmic improvements are largely orthogonal to your interface change; the new interface may just call the improved algorithms.

-- wli

Executive summary: I wrote a benchmark to compare /proc and nproc performance. The results are as expected: Parsing even the most simple strings is expensive. /proc performance does not scale if we have to open and close many files, which is the common case.

In a situation with many processes p and fields/files f the delivery overhead is roughly O(p) for nproc and O(p*f) for /proc.

The difference becomes even more pronounced if a /proc file request triggers an expensive in-kernel computation for fields that are not of interest but part of the file, or if human-readable files need to be parsed.

Benchmark: I chose the most favorable scenario for /proc I could think
of: Reading a single, easy to parse file per process and find every data item useful. I picked /proc/pid/statm. For nproc, I chose seven fields that are calculated with the same resource usage as the fields in statm:
NPROC_VMSIZE, NPROC_VMLOCK, NPROC_VMRSS, NPROC_VMDATA, NPROC_VMSTACK, NPROC_VMEXE, and NPROC_VMLIB.

Numbers:
* The first run is basically lseek+read:
/proc/pid/statm for 1000 processes, 1000 times, lseek CPU time : 7.080000s
Wall time: 7.636732s

* The second run adds a simple sscanf call to dump seven values into seven variables:
/prod/pid/statm for 1000 processes, 1000 times, lseek (scanf) CPU time : 10.230000s
Wall time: 10.958432s

* If we watch p processes with f files each, we typically hit the file descriptor limit before p * f == 1024. From then on, lseek is useless, we have to resort to opening and closing files:
/prod/pid/statm for 1000 processes, 1000 times, open
CPU time : 14.920000s
Wall time: 16.087339s

* Again, parsing the string comes at a cost:
/prod/pid/statm for 1000 processes, 1000 times, open (scanf) CPU time : 18.110000s
Wall time: 19.457451s

* What happens if we need to read 2 simple /proc files (14 fields) per process?
/prod/pid/statm (2x) for 1000 processes, 1000 times, open (scanf) CPU time : 30.250000s
Wall time: 32.650314s

* 10000 processes at 3 files each (27 fields) /prod/pid/statm (3x) for 10000 processes, 1000 times, open (scanf) CPU time : 450.630000s
Wall time: 500.265503s

* nproc delivering said 7 fields:
nproc for 1000 processes, 1000 times, one process per request CPU time : 7.910000s
Wall time: 8.473371s

* 200 processes per request, but still 1000 reply messages. If we stuffed a bunch of them into every message, performance would improve further.
nproc for 1000 processes, 1000 times, 200 processes per request CPU time : 6.350000s
Wall time: 6.817391s

* There's no large penalty if we need additional fields:
14 nproc fields for 1000 processes, 1000 times, one process per request CPU time : 8.680000s
Wall time: 9.328828s

27 nproc fields for 10000 processes, 1000 times, one process per request CPU time : 88.270000s
Wall time: 98.664330s

Roger

These numbers are somewhat at variance with my experience in the area, as I see that the internal algorithms actually dominate the runtime of the /proc/ algorithms. Could you describe the processes used for the benchmarks, e.g. typical /proc/$PID/status and /proc/$PID/maps for them?

-- wli

The status/maps numbers below are not only typical, but identical for all tasks. I'm forking off a defined number of children and then query their status from the parent.

Because I was interested in delivery overhead, I built on purpose a benchmark without computationally expensive fields. Expensive field computation hurts /proc more than nproc because the latter allows you to have only the currently needed fields computed.

Roger

Name:   nprocbench
State:  T (stopped)
SleepAVG:       0%
Tgid:   6400
Pid:    6400
PPid:   2120
TracerPid:      0
Uid:    1000    1000    1000    1000
Gid:    100     100     100     100
FDSize: 32
Groups: 4 10 11 18 19 20 27 100 250 
VmSize:     1336 kB
VmLck:         0 kB
VmRSS:       304 kB
VmData:      144 kB
VmStk:        16 kB
VmExe:        12 kB
VmLib:      1140 kB
Threads:        1
SigPnd: 0000000000000000
ShdPnd: 0000000000080000
SigBlk: 0000000000000000
SigIgn: 0000000000000000
SigCgt: 0000000000000000
CapInh: 0000000000000000
CapPrm: 0000000000000000
CapEff: 0000000000000000

08048000-0804b000 r-xp 00000000 03:45 160990 /home/rl/nproc/nprocbench
0804b000-0804c000 rw-p 00002000 03:45 160990 /home/rl/nproc/nprocbench
0804c000-0806d000 rw-p 0804c000 00:00 0
40000000-40013000 r-xp 00000000 03:42 11356336 /lib/ld-2.3.3.so
40013000-40014000 rw-p 00012000 03:42 11356336 /lib/ld-2.3.3.so
40014000-40015000 rw-p 40014000 00:00 0
40032000-4013c000 r-xp 00000000 03:42 11356337 /lib/libc-2.3.3.so
4013c000-40140000 rw-p 00109000 03:42 11356337 /lib/libc-2.3.3.so
40140000-40142000 rw-p 40140000 00:00 0
bfffc000-c0000000 rw-p bfffc000 00:00 0
ffffe000-fffff000 ---p 00000000 00:00 0

Okay, these explain some of the difference. I usually see issues with around 10000 processes with fully populated virtual address spaces and several hundred vmas each, varying between 200 to 1000, mostly concentrated at somewhere just above 300.

-- wli

I agree, that should make quite a difference. As you said, we are working on orthogonal areas: My current focus is on data delivery (sane semantics and minimal overhead), while you seem to be more interested in better data gathering.

I profiled "top -d 0 -b > /dev/null" for about 100 and 10^5 processes.

When monitoring 100 (real-world) processes, /proc specific overhead (_IO_vfscanf_internal, number, __d_lookup, vsnprintf, etc.) amounts to about one third of total resource usage.

==> 100 processes: top -d 0 -b > /dev/null <==
CPU: CPU with timer interrupt, speed 0 MHz (estimated) Profiling through timer interrupt

samples  %        image name               symbol name
20439    12.2035  libc-2.3.3.so            _IO_vfscanf_internal
15852     9.4647  vmlinux                  number
11635     6.9469  vmlinux                  task_statm
9286      5.5444  libc-2.3.3.so            _IO_vfprintf_internal
9128      5.4500  vmlinux                  proc_pid_stat
5395      3.2212  vmlinux                  __d_lookup
4738      2.8289  vmlinux                  vsnprintf
4123      2.4617  libc-2.3.3.so            _IO_default_xsputn_internal
4110      2.4540  libc-2.3.3.so            __i686.get_pc_thunk.bx
3712      2.2163  libc-2.3.3.so            _IO_putc_internal
3504      2.0921  vmlinux                  link_path_walk
3417      2.0402  libc-2.3.3.so            ____strtoul_l_internal
3363      2.0079  libc-2.3.3.so            ____strtol_l_internal
2250      1.3434  libncurses.so.5.4        _nc_outch
2116      1.2634  libc-2.3.3.so            _IO_sputbackc_internal
2006      1.1977  top                      task_show
1851      1.1052  vmlinux                  pid_revalidate

With 10^5 additional dummy processes, resource usage is dominated by attempts to get a current list of pids. My own benchmark walked a list of known pids, so that was not an issue. I bet though that nproc can provide more efficient means to get such a list than getdents (we could even allow a user to ask for a message on process creation/kill).

So basically that's just another place where nproc-based tools would trounce /proc-based ones (that piece is vaporware today, though).

==> 10000 processes: top -d 0 -b > /dev/null <==
CPU: CPU with timer interrupt, speed 0 MHz (estimated) Profiling through timer interrupt

samples  %        image name               symbol name
35855    36.0707  vmlinux                  get_tgid_list
9366      9.4223  vmlinux                  pid_alive
7077      7.1196  libc-2.3.3.so            _IO_vfscanf_internal
5386      5.4184  vmlinux                  number
3664      3.6860  vmlinux                  proc_pid_stat
3077      3.0955  libc-2.3.3.so            _IO_vfprintf_internal
2136      2.1489  vmlinux                  __d_lookup
1720      1.7303  vmlinux                  vsnprintf
1451      1.4597  libc-2.3.3.so            __i686.get_pc_thunk.bx
1409      1.4175  libc-2.3.3.so            _IO_default_xsputn_internal
1258      1.2656  libc-2.3.3.so            _IO_putc_internal
1225      1.2324  vmlinux                  link_path_walk
1210      1.2173  libc-2.3.3.so            ____strtoul_l_internal
1199      1.2062  vmlinux                  task_statm
1157      1.1640  libc-2.3.3.so            ____strtol_l_internal
794       0.7988  libc-2.3.3.so            _IO_sputbackc_internal
776       0.7807  libncurses.so.5.4        _nc_outch

The remaining profiles are for two benchmarks from my previous message.

Field computation is more prominent than with top because the benchmark uses a known list of pids and parsing is kept at a trivial level.

==> /prod/pid/statm (2x) for 10000 processes <==
CPU: CPU with timer interrupt, speed 0 MHz (estimated) Profiling through timer interrupt

samples  %        image name               symbol name
7430      9.9485  libc-2.3.3.so            _IO_vfscanf_internal
6195      8.2948  vmlinux                  __d_lookup
5477      7.3335  vmlinux                  task_statm
5082      6.8046  vmlinux                  number
3227      4.3208  vmlinux                  link_path_walk
3050      4.0838  libc-2.3.3.so            ____strtol_l_internal
2116      2.8332  libc-2.3.3.so            _IO_vfprintf_internal
2064      2.7636  vmlinux                  vsnprintf
1664      2.2280  vmlinux                  atomic_dec_and_lock
1551      2.0767  vmlinux                  task_dumpable
1497      2.0044  vmlinux                  pid_revalidate
1419      1.9000  vmlinux                  system_call
1401      1.8759  vmlinux                  pid_alive
1244      1.6657  libc-2.3.3.so            _IO_sputbackc_internal
1175      1.5733  vmlinux                  dnotify_parent
1060      1.4193  libc-2.3.3.so            _IO_default_xsputn_internal
922       1.2345  vmlinux                  file_move

nproc removes most of the delivery overhead so field computation is now dominant. Strictly speaking, it should be even higher because the benchmarks requests the same fields three times, but they only get computed once in such a case.

==> 27 nproc fields for 10000 processes, one process per request <==
CPU: CPU with timer interrupt, speed 0 MHz (estimated) Profiling through timer interrupt

samples  %        image name               symbol name
7647     25.0894  vmlinux                  __task_mem
2125      6.9720  vmlinux                  find_pid
1884      6.1813  vmlinux                  nproc_pid_fields
1488      4.8820  vmlinux                  __task_mem_cheap
1161      3.8092  vmlinux                  mmgrab
978       3.2088  vmlinux                  netlink_recvmsg
944       3.0972  vmlinux                  alloc_skb
935       3.0677  vmlinux                  __might_sleep
751       2.4640  vmlinux                  nproc_select_pid
738       2.4213  vmlinux                  system_call
691       2.2671  vmlinux                  skb_dequeue
636       2.0867  vmlinux                  netlink_sendmsg
630       2.0670  vmlinux                  __copy_from_user_ll
624       2.0473  vmlinux                  sockfd_lookup
621       2.0375  vmlinux                  kfree
602       1.9751  vmlinux                  __reply_size
523       1.7159  vmlinux                  fget

Roger

Yes, there doesn't seem to be any conflict between the code we're working on. These benchmark results are very useful for quantifying the relative importance of the overheads under more typical conditions.

Lexical analysis is cpu-intensive, probably due to the cache misses taken while traversing the strings. This is likely inherent in string processing interfaces.

get_tgid_list() is a sad story I don't have time to go into in depth. The short version is that larger systems are extremely sensitive to hold time for writes on the tasklist_lock, and this being on scales not needing SGI participation to tell us (though scales beyond personal financial resources still).

scanf() is still very pronounced here; I wonder how well-optimized glibc's implementation is, or if otherwise it may be useful to circumvent it with a more specialized parser if its generality requirements preclude faster execution.

It looks like I'm going after the right culprit(s) for the lower-level algorithms from this.

-- wli

I am confident that this problem (as far as process monitoring is concerned) could be addressed with differential notification.

I'd much rather remove unnecessary overhead than optimize code for overhead processing. Note that number() takes out 7% and that's the _kernel_ printing numbers for user space to parse back. And __d_lookup is another /proc souvenir you get to keep as long as you use /proc.

Well __task_mem is promiment here because I don't call other computation functions. vmstat ain't cheap, and wchan is horribly expensive if the kernel does the ksym translation. Etc. pp.

Roger

I'm a bit squeamish about that given that mmlist_lock and tasklist_lock are both problematic and yet another global structure to fiddle with in the process creation and destruction path threatens similar trouble.

Also, what guarantee is there that the notification events come sufficiently slowly for a single task to process, particularly when that task may not have a whole cpu's resources to marshal to the task? Queueing them sounds less than ideal due to resource consumption, and if notifications are dropped most of the efficiency gains are lost. So I question that a bit.

I have a vague notion that userspace should intelligently schedule inquiries so requests are made at a rate the app can process and so that the app doesn't consume excessive amounts of cpu. In such an arrangement screen refresh events don't trigger a full scan of the tasklist, but rather only an incremental partial rescan of it, whose work is limited for the above cpu bandwidth concerns.

I'm expecting very very long lifetimes for legacy kernel versions and userspace predating the merge of nproc, so it's not entirely irrelevant, though backports aren't exactly something I relish.

task_mem() is generally prominent when the processes have large numbers of vmas, and also due to acquisition of ->mmap_sem.

-- wli

The numbers looks so bad that for many cases it's going to be a significant win if we simply call nproc_send_note in said paths. But I'll admit that I've been entertaining thoughts about a global queue or something to send notifications in batches.

A more likely guarantee is that a process that can't keep up with differential updates won't be able to process the whole list, either. Well, unless the system is loaded with tons of short-lived processes that wouldn't even make the full process list by the time it's pulled. But in such a case, a complete list of task won't do you much good, either, because by the time you are ready to query the kernel for details the tasks are gone.

Point. Task discovery is not an exact science anyway, though.

I'd still expect differential notification to be useful in most non-pathological cases, but I concede it's nowhere as clear-cut as nproc per se is.

While I'm not sure I understand how that partial rescan (or its limits) would be defined, I agree with the general idea. There is indeed plenty of room for improvement in a smart user space. For instance, most apps show only the top n processes. So if an app shows the top 20 memory users, it could use nproc to get a complete list of pid+vmrss, and then request all the expensive fields only for the top 20 in that list.

Uhm... Optimized string parsing would require updated user space anyway. OTOH, I can buy the legacy kernel argument, so if you want to rewrite the user space tools, go wild :-). You may find that there are issues more serious than string parsing:

$ ps --version
procps version 3.2.3
$ ps -o pid
  PID
 2089
 2139
$ strace ps -o pid 2>&1|grep 'open("/proc/'|wc -l
325

<whine>

Makes sense. I just wanted to make sure I wasn't misleading you.

Roger

...

When the reader falls behind, keep supplying differential updates as long as practical. When this starts to eat up lots of memory, switch to supplying the full list until the reader catches up again.

If you won't scan, why update the display? This boils down to simply setting a lower refresh rate or using "nice".

This is crummy. It's done for wchan, since that is so horribly expensive, but I'm not liking the larger race condition window. Remember that PIDs get reused. There isn't a generation counter or UUID that can be checked.

While "pid" makes a nice extreme example, note that ps must handle arbitrary cases like "pmem,comm,wchan,ppid,session".

Now, I direct your attention to "Introduction to Algorithms", by Cormen, Leiserson, and Rivest. Find the section entitled "The set-covering problem". It's page 974, section 37.3, in my version of the book. An example of this would be the determination of the minimum set of /proc files needed to supply some required set of process attributes.

Look familiar? It's NP-hard. To me, that just sounds bad. :-)

While there are decent (?) approximations that run in polynomial time, they are generally overkill. It is very common to need both the stat and status files. Selection, sorting, and display all may require data.

But hey, we can go ahead and compute NP-hard problems in userspace if that makes the kernel less complicated. :-) Just remember that if I say "this is hard", I mean it.

You shouldn't have to try to scan the set of all tasks in any bounded period of time or rely on differential updates. Scanning some part of the list of a bounded size, updating the state based on what was scanned, and reporting the rest as if it hadn't changed is the strategy I'm describing.

Some updates can be captured, merely not all. Updating the state given what was captured during the partial scan and then displaying the state derived from what could be captured in the refresh interval is more useful than being nonfunctional at the lower refresh intervals or needlessly beating the kernel in some futile attempt to exhaustively search an impossibly huge dataset in some time bound that can't be satisfied.

One shouldn't really need to care; periodically rechecking the fields of an active pid should suffice. You don't really care whether it's the same task or not, just that the fields are up-to-date and whether any task with that pid exists.

[...]

Actually, the problem size is so small it shouldn't be problematic. There are only 13 /proc/ files associated with a process, so exhaustive search over 2**13 - 1 == 8191 nonempty subsets, e.g. queueing by size and checking for the satisfiability of the reporting, will suffice.

-- wli

That's defective. Users will not like it.

nice -n 19 top

People use the procps tools to kill processes.
Bad data leads to bad decisions.

Nice! Checking for satisfiability is only NP-complete...

I do get your point, but I expect to see more /proc files as time passes. Also, there is the issue of maintainability.

Example 1: It has crossed my mind to add separate files for the least security-critical data, so that an SE Linux system with moderate security could provide some minimal amount of basic info to normal users.

Example 2: There could be files containing only data that is easy to generate or that needs the same locking.

Even with the "ps -o pid" example given, opening /proc/*/stat is required to get the tty. Opening /proc/*/status is nearly required; one can do stat() on the directory to get that via st_uid though.

Scarcely. The task can't be done in realtime. The data will be stale by the time it's reported anyway. Limiting the amount of sampling done is vastly superior to beating the kernel's reporting interfaces to death in a totally futile attempt to achieve infeasible consistencies, burning ridiculous amounts of cpu in the process, and reporting gibberish in the end anyway.

No, hard cpu limits are required, and even then it just spews gibberish and very slowly. The current algorithms are nonfunctional with any substantial number of processes.

Refusal to rate limit sampling doesn't make the data more coherent in the presence of large numbers of tasks.

No, that's not general satisfiability. Each field to be reported needs at least one out of some set of subsets of /proc/ files associated with a process to be includes in those parsed. Checking for inclusion of one of a field's required subsets for each field suffices. The number of subsets of /proc/ files from which a field is calculable is bounded by some small constant. It must be constant, as there are a finite number of fields, and the constant is small, as this is some specific set and the precise upper bound can be found, and if/when it is found, it is very likely to be well under a tenth of the total number of subsets of /proc/ files associated with a process.

I don't have a whole lot to say on this subject. These sound reasonable.

-- wli

I think it should be up to the reader to request stuff, so I'd probably just have the kernel notify the client that there won't be any more differential updates. Then the client can decide what to do now.

But I'd have to play around with this to see what works.

The races left with nproc are much smaller. There is of course the question of whether the pid still exists by the time you query the kernel about it. But you get all the information in one go (although the process may still disappear while the kernel prepares the requested info).

[...]

Entertaining, but you missed the point: I am not terribly impressed with the fact that ps opens two files (stat, statm) for _every_ _single_ _process_ if all I want to know is, say, the name of PID 42 (example taken from ps(1): ps -p 42 -o comm=).

And FWIW, you don't need the "minimum set of /proc files needed to supply some required set of process attributes". Any set that supplies the required fields will do, and you can get an excellent approximation in O(n).

I suspect Cormen, Leiserson, and Rivest would take exception with your assertion that ps tools can't be improved. Or even that doing so is hard.

Roger

You got that, and you didn't like it.

I'm sure it wouldn't be hard to hack up some special-case optimization for the cases you've listed. As soon as I do so, you'll find another special case. Ultimately, you ARE asking to have procps solve the NP-hard set-covering problem.

There are several good reasons to not go down that path. The potential for increasing numbers of /proc files in the future is one. Another is the very limited benefit; typical ps usage does require much of that data. Maintainability is yet another reason; ps does more than just spit out the data. It is very useful to have a decent selection of data items that will always be available for process selection, sorting, and any other use. The potential for adding bugs is great.

That said, I do at times tweak the code used to select data sources. Perhaps I should add a new /proc/*/basics file for the most popular items. This would make fancy set-covering choices more profitable.

It shouldn't surprise that I am not keen on making any semantic changes to /proc in order to help tools. nproc is a vastly superior interface.

Roger

I just wanted to call your attention to the kallsyms speedup patch that is now on the -mm tree.

It should improve wchan speed. My benchmarks for kallsyms_lookup (the function that was responsible for the wchan time) went from 1340us to 0.5us.

So maybe this is enough not to make wchan a special case anymore...

Paulo Marques - www.grupopie.com

To err is human, but to really foul things up requires a computer.
Farmers' Almanac, 1978

This seems to go wrong on big-endian machines; any chance you could look over your stuff and try to figure out what endianness issues it may have?

-- wli

I went over the code but at a first glance couldn't find a notorius trouble spot. I don't have big-endian hardware myself so this is hard to test.

Just a few questions to help me out in finding the problem:

- is this really an endianess problem or is it a 64-bit integer problem?

- are you cross compiling the kernel?

Thanks in advance,

Paulo Marques - www.grupopie.com

To err is human, but to really foul things up requires a computer.
Farmers' Almanac, 1978

Works fine on x86-64 and alpha. Prints gibberish on sparc64.

No. All native.

-- wli

Can you send me an ".tmp_kallsyms2.S" obtained after a kernel build on a sparc64, so that I can isolate the problem between scripts/kallsyms.c and kernel/kallsyms.c? (maybe gzip'ed and in private, because this can be a big file...)

Thanks for all the help in debugging this.

Paulo Marques - www.grupopie.com

To err is human, but to really foul things up requires a computer.
Farmers' Almanac, 1978

Thanks, Roger and William, for your good work here. I'm sure that SGI's big bertha's will benefit.

In glancing at the get_tgid_list() I see it is careful to only pick off 20 (PROC_MAXPIDS) slots at a time. But elsewhere in the kernel, I see several uses of "do_each_thread()" which rip through the entire task list in a single shot.

Is there a simple explanation for why it is ok in one place to take on the entire task list in a single sweep, but in another it is important to drop the lock every 20 slots?

(1) the work that had to be done by proc_pid_readdir(), the caller of get_tgid_list(), required dropping the task list lock, and
(2) so the harvested tgid's had to be stashed in a temp buffer.

So perhaps the reason for not doing this in a single pass is:
(3) it was not doable or not desirable (which one?) to size that temp buffer large enough to hold all the harvested tgid's in one pass.

But my understanding is losing the scent of the trail at this point.

                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373

PROC_MAXPIDS is the size of the buffer used to temporarily store the pid's while doing user copies, so that potentially blocking operations may be done to transmit the pid's to userspace.

Introducing another whole-tasklist scan, even if feasible, is probably not a good idea.

Using a larger, dynamically-allocated buffer may be better. e.g. allocating a page to buffer pid's with.

A solution to the problem of the quadratic algorithm I wrote long ago restructured the tasklist as an rbtree so that the position in the tasklist could be recovered in O(lg(n)) time. Unfortunately, this increases the write hold time of tasklist_lock.

-- wli

[...]

I'm not sure whether I should participate in that discussion. I'll risk discrediting nproc with wild speculations on a subject I haven't really looked into yet. Ah well...

As far as nproc (and process monitoring) is concerned, we aren't really interested in walking a complete process list. All we care about is which pids exist right now. How about a bit field, maintained by the kernel, to indicate for each pid whether it exists or not? This would amount to 4 KiB by default and 512 KiB for PID_MAX_LIMIT (4 million processes). Maintenance cost would be one atomic bit operation per process creation/deletion. No contested locks.

The list for the nproc user could be prepared based on the bit field (or simply memcpy'd), no tasklist_lock or walking linked lists required.

What am I missing?

Roger

There isn't much to speculate about here; reducing the arrival rate to tasklist_lock is okay, but it can't be held forever or use unbounded allocations or anything like that.

The pid bitmap could be exported to userspace rather easily.

-- wli

I implemented an "all processes" selector based on that. Remaining pieces are access control and a method for dumping large amounts of data (10 - 1000 KB) to user space.

Roger

This posting demonstrates a new method of monitoring all processes in a large system.

You may remember what a /proc based tool does when monitoring some 10^5 processes -- it spends its time in the kernel hanging on to a read task_list_lock:

==> 10000 processes: top -d 0 -b > /dev/null <==
CPU: CPU with timer interrupt, speed 0 MHz (estimated) Profiling through timer interrupt

samples  %        image name               symbol name
35855    36.0707  vmlinux                  get_tgid_list
9366      9.4223  vmlinux                  pid_alive
7077      7.1196  libc-2.3.3.so            _IO_vfscanf_internal
5386      5.4184  vmlinux                  number
3664      3.6860  vmlinux                  proc_pid_stat
3077      3.0955  libc-2.3.3.so            _IO_vfprintf_internal
2136      2.1489  vmlinux                  __d_lookup
1720      1.7303  vmlinux                  vsnprintf
1451      1.4597  libc-2.3.3.so            __i686.get_pc_thunk.bx
1409      1.4175  libc-2.3.3.so            _IO_default_xsputn_internal
1258      1.2656  libc-2.3.3.so            _IO_putc_internal
1225      1.2324  vmlinux                  link_path_walk
1210      1.2173  libc-2.3.3.so            ____strtoul_l_internal
1199      1.2062  vmlinux                  task_statm
1157      1.1640  libc-2.3.3.so            ____strtol_l_internal
794       0.7988  libc-2.3.3.so            _IO_sputbackc_internal
776       0.7807  libncurses.so.5.4        _nc_outch

Here's a profile for an nproc based tool monitoring the same set of processes:

==> 10000 processes: nprocbench <==
CPU: CPU with timer interrupt, speed 0 MHz (estimated) Profiling through timer interrupt

samples  %        app name                 symbol name
8641     24.8626  vmlinux                  __task_mem
2778      7.9931  vmlinux                  find_pid
2536      7.2968  vmlinux                  finish_task_switch
1872      5.3863  vmlinux                  netlink_recvmsg
1637      4.7101  vmlinux                  nproc_pid_fields
1373      3.9505  vmlinux                  __wake_up
1218      3.5045  vmlinux                  __copy_to_user_ll
1134      3.2628  vmlinux                  __task_mem_cheap
944       2.7162  vmlinux                  mmgrab
876       2.5205  vmlinux                  nproc_ps_do_pid
568       1.6343  vmlinux                  skb_dequeue
526       1.5135  libc-2.3.3.so            __recv
514       1.4789  vmlinux                  alloc_skb
510       1.4674  vmlinux                  __might_sleep
485       1.3955  vmlinux                  skb_release_data
463       1.3322  vmlinux                  netlink_attachskb
363       1.0445  vmlinux                  sys_recvfrom

Resource usage is now dominated by field computation, rather than by delivery overhead. By now it should be clear that nproc is not only a cleaner interface with lower overhead for tools, it also scales a lot better than /proc.

Roger

[...]

The most crucial issue for larger systems is removing the rather easily triggerable rwlock starvation. Perhaps dipankar's /proc/ -only tasklist RCU patch can resolve that.

[...]

With this in hand we can probably ignore the /proc/ -related efficiency issues in favor of any method preventing the rwlock starvation, e.g. dipankar's /proc/ -only tasklist RCU patch.

-- wli