Add /proc/pid_generation

This change adds a per-pid-namespace 64-bit generation number, incremented on PID rollover, and exposes it via a new proc file /proc/pid_generation. By examining this file before and after /proc enumeration, user code can detect the potential reuse of a PID and restart the task enumeration process, repeating until it gets a coherent snapshot.

PID rollover ought to be rare, so in practice, scan repetitions will be rare.

Quoted 7 lines · Daniel Colascione

This change adds a per-pid-namespace 64-bit generation number, incremented on PID rollover, and exposes it via a new proc file /proc/pid_generation. By examining this file before and after /proc enumeration, user code can detect the potential reuse of a PID and restart the task enumeration process, repeating until it gets a coherent snapshot.

Quoted 2 lines

PID rollover ought to be rare, so in practice, scan repetitions will be rare.

Then why does it need to be 64-bit?

Quoted 9 lines · Matthew Wilcox

Quoted 7 lines · Daniel Colascione

This change adds a per-pid-namespace 64-bit generation number, incremented on PID rollover, and exposes it via a new proc file /proc/pid_generation. By examining this file before and after /proc enumeration, user code can detect the potential reuse of a PID and restart the task enumeration process, repeating until it gets a coherent snapshot.

Quoted 4 lines

Quoted 2 lines

PID rollover ought to be rare, so in practice, scan repetitions will be rare.

Then why does it need to be 64-bit?

[Resending because of accidental HTML. I really need to switch to a better email client.]

Because 64 bits is enough for anyone. :-) A u64 is big enough that we'll never observe an overflow on a running system, and PID namespaces are rare enough that we won't miss the four extra bytes we use by upgrading from a u32. And after reading about some security problems caused by too-clever handling of 32-bit rollover, I'd rather the code be obviously correct than save a trivial amount of space.

Quoted 18 lines · Daniel Colascione

Quoted 9 lines · Matthew Wilcox

Quoted 7 lines · Daniel Colascione

This change adds a per-pid-namespace 64-bit generation number, incremented on PID rollover, and exposes it via a new proc file /proc/pid_generation. By examining this file before and after /proc enumeration, user code can detect the potential reuse of a PID and restart the task enumeration process, repeating until it gets a coherent snapshot.

Quoted 4 lines

Quoted 2 lines

PID rollover ought to be rare, so in practice, scan repetitions will be rare.

Then why does it need to be 64-bit?

[Resending because of accidental HTML. I really need to switch to a better email client.]

Quoted 6 lines

Because 64 bits is enough for anyone. :-) A u64 is big enough that we'll never observe an overflow on a running system, and PID namespaces are rare enough that we won't miss the four extra bytes we use by upgrading from a u32. And after reading about some security problems caused by too-clever handling of 32-bit rollover, I'd rather the code be obviously correct than save a trivial amount of space.

I don't think you understand how big 4 billion is. If it happens once a second, it will take 136 years for a 2^32 count to roll over. How often does a PID roll over happen?

Trace analysis code needs a coherent picture of the set of processes and threads running on a system. While it's possible to enumerate all tasks via /proc, this enumeration is not atomic. If PID numbering rolls over during snapshot collection, the resulting snapshot of the process and thread state of the system may be incoherent, confusing trace analysis tools. The fundamental problem is that if a PID is reused during a userspace scan of /proc, it's impossible to tell, in post-processing, whether a fact that the userspace /proc scanner reports regarding a given PID refers to the old or new task named by that PID, as the scan of that PID may or may not have occurred before the PID reuse, and there's no way to "stamp" a fact read from the kernel with a trace timestamp.

This change adds a per-pid-namespace 64-bit generation number, incremented on PID rollover, and exposes it via a new proc file /proc/pid_gen. By examining this file before and after /proc enumeration, user code can detect the potential reuse of a PID and restart the task enumeration process, repeating until it gets a coherent snapshot.

PID rollover ought to be rare, so in practice, scan repetitions will be rare.

include/linux/pid.h +0 -0

 extern void free_pid(struct pid *pid);
 extern void disable_pid_allocation(struct pid_namespace *ns);
 
...
 

include/linux/pid.h +6 -0

+	seq_printf(m, "%llu\n", generation);
+	return 0;
+
+};
+#endif
+
 void __init pid_idr_init(void)
 {
 	/* Verify no one has done anything silly: */

Quoted 20 lines · On Wed, 21 Nov 2018 12:54:20 -0800 Daniel Colascione <[email protected]> wrote:

Trace analysis code needs a coherent picture of the set of processes and threads running on a system. While it's possible to enumerate all tasks via /proc, this enumeration is not atomic. If PID numbering rolls over during snapshot collection, the resulting snapshot of the process and thread state of the system may be incoherent, confusing trace analysis tools. The fundamental problem is that if a PID is reused during a userspace scan of /proc, it's impossible to tell, in post-processing, whether a fact that the userspace /proc scanner reports regarding a given PID refers to the old or new task named by that PID, as the scan of that PID may or may not have occurred before the PID reuse, and there's no way to "stamp" a fact read from the kernel with a trace timestamp.

This change adds a per-pid-namespace 64-bit generation number, incremented on PID rollover, and exposes it via a new proc file /proc/pid_gen. By examining this file before and after /proc enumeration, user code can detect the potential reuse of a PID and restart the task enumeration process, repeating until it gets a coherent snapshot.

Quoted 2 lines

PID rollover ought to be rare, so in practice, scan repetitions will be rare.

In general, tracing is a rather specialized thing. Why is this very occasional confusion a sufficiently serious problem to warrant addition of this code?

Which userspace tools will be using pid_gen? Are the developers of those tools signed up to use pid_gen?

include/linux/pid.h extern struct pid *find_ge_pid(int nr, struct pid_namespace *); · line 115

Quoted 7 lines

include/linux/pid.h +1 -0

@@ -112,6 +112,7 @@ extern struct pid *find_ge_pid(int nr, struct pid_namespace *);
 int next_pidmap(struct pid_namespace *pid_ns, unsigned int last);
 
 extern struct pid *alloc_pid(struct pid_namespace *ns);
+extern u64 read_pid_generation(struct pid_namespace *ns);

pig_generation_read() would be a better (and more idiomatic) name.

Quoted 6 lines

include/linux/pid.h +0 -0

 extern void free_pid(struct pid *pid);
 extern void disable_pid_allocation(struct pid_namespace *ns);
 
...

include/linux/pid.h

Quoted 10 lines

include/linux/pid.h +10 -0

+u64 read_pid_generation(struct pid_namespace *ns)
+{
+     u64 generation;
+
+
+     spin_lock_irq(&pidmap_lock);
+     generation = ns->generation;
+     spin_unlock_irq(&pidmap_lock);
+     return generation;
+}

What is the spinlocking in here for? afaict the only purpose it serves is to make the 64-bit read atomic, so it isn't needed on 32-bit?

include/linux/pid.h struct pid *find_ge_pid(int nr, struct pid_namespace *ns) · line 470

Quoted 12 lines

void disable_pid_allocation(struct pid_namespace *ns)

 {
      spin_lock_irq(&pidmap_lock);

include/linux/pid.h +5 -0

@@ -449,6 +463,17 @@ struct pid *find_ge_pid(int nr, struct pid_namespace *ns)
      return idr_get_next(&ns->idr, &nr);
 }
 
+#ifdef CONFIG_PROC_FS
+static int pid_generation_show(struct seq_file *m, void *v)
+{
+     u64 generation =
+             read_pid_generation(proc_pid_ns(file_inode(m->file)));

        u64 generation;

        generation = read_pid_generation(proc_pid_ns(file_inode(m->file)));

is a nicer way of avoiding column wrap.

Quoted 11 lines

include/linux/pid.h +6 -0

+     seq_printf(m, "%llu\n", generation);
+     return 0;
+
+};
+#endif
+
 void __init pid_idr_init(void)
 {
      /* Verify no one has done anything silly: */

@@ -465,4 +490,13 @@ void __init pid_idr_init(void)
 

include/linux/pid.h void __init pid_idr_init(void) · line 498

Quoted 8 lines

include/linux/pid.h +6 -0

      init_pid_ns.pid_cachep = KMEM_CACHE(pid,
                      SLAB_HWCACHE_ALIGN | SLAB_PANIC | SLAB_ACCOUNT);
+
+}
+
+void __init pid_proc_init(void)
+{
+     /* pid_idr_init is too early, so get a separate init function. */

s/get a/use a/

include/linux/pid.h void __init pid_idr_init(void) · line 502

Quoted 4 lines

include/linux/pid.h +3 -0

+#ifdef CONFIG_PROC_FS
+     WARN_ON(!proc_create_single("pid_gen", 0, NULL, pid_generation_show));
+#endif
 }

This whole function could vanish if !CONFIG_PROC_FS. Doesn't matter much with __init code though.

Quoted 14 lines · Andrew Morton

kernel/pid.c struct pid *alloc_pid(struct pid_namespace *ns) · line 261

Quoted 10 lines · On Wed, 21 Nov 2018 12:54:20 -0800 Daniel Colascione <[email protected]> wrote:

kernel/pid.c +10 -0

+u64 read_pid_generation(struct pid_namespace *ns)
+{
+     u64 generation;
+
+
+     spin_lock_irq(&pidmap_lock);
+     generation = ns->generation;
+     spin_unlock_irq(&pidmap_lock);
+     return generation;
+}

What is the spinlocking in here for? afaict the only purpose it serves is to make the 64-bit read atomic, so it isn't needed on 32-bit?

ITYM the spinlock is necessary *only* on 32-bit, since 64-bit architectures have atomic 64-bit reads, and 64-bit reads on 32-bit architectures can tear. This function isn't a particularly hot path, so I thought consistency across architectures would be more valuable than avoiding the lock on some systems.

Quoted 16 lines · Daniel Colascione

Quoted 14 lines · Andrew Morton

kernel/pid.c struct pid *alloc_pid(struct pid_namespace *ns) · line 261

Quoted 10 lines · On Wed, 21 Nov 2018 12:54:20 -0800 Daniel Colascione <[email protected]> wrote:

kernel/pid.c +10 -0

+u64 read_pid_generation(struct pid_namespace *ns)
+{
+     u64 generation;
+
+
+     spin_lock_irq(&pidmap_lock);
+     generation = ns->generation;
+     spin_unlock_irq(&pidmap_lock);
+     return generation;
+}

What is the spinlocking in here for? afaict the only purpose it serves is to make the 64-bit read atomic, so it isn't needed on 32-bit?

Quoted 5 lines

ITYM the spinlock is necessary *only* on 32-bit, since 64-bit architectures have atomic 64-bit reads, and 64-bit reads on 32-bit architectures can tear. This function isn't a particularly hot path, so I thought consistency across architectures would be more valuable than avoiding the lock on some systems.

Linux has atomic64_t/atomic64_read()/atomic64_inc() for this, which should automatically do the right thing - processor-supported atomic ops when possible, spinlock otherwise.

Quoted 23 lines · Andrew Morton

Quoted 20 lines · On Wed, 21 Nov 2018 12:54:20 -0800 Daniel Colascione <[email protected]> wrote:

Trace analysis code needs a coherent picture of the set of processes and threads running on a system. While it's possible to enumerate all tasks via /proc, this enumeration is not atomic. If PID numbering rolls over during snapshot collection, the resulting snapshot of the process and thread state of the system may be incoherent, confusing trace analysis tools. The fundamental problem is that if a PID is reused during a userspace scan of /proc, it's impossible to tell, in post-processing, whether a fact that the userspace /proc scanner reports regarding a given PID refers to the old or new task named by that PID, as the scan of that PID may or may not have occurred before the PID reuse, and there's no way to "stamp" a fact read from the kernel with a trace timestamp.

This change adds a per-pid-namespace 64-bit generation number, incremented on PID rollover, and exposes it via a new proc file /proc/pid_gen. By examining this file before and after /proc enumeration, user code can detect the potential reuse of a PID and restart the task enumeration process, repeating until it gets a coherent snapshot.

Quoted 6 lines

Quoted 2 lines

PID rollover ought to be rare, so in practice, scan repetitions will be rare.

In general, tracing is a rather specialized thing. Why is this very occasional confusion a sufficiently serious problem to warrant addition of this code?

I wouldn't call tracing a specialized thing: it's important enough to justify its own summit and a whole ecosystem of trace collection and analysis tools. We use it in every day in Android. It's tremendously helpful for understanding system behavior, especially in cases where multiple components interact in ways that we can't readily predict or replicate. Reliability and precision in this area are essential:
retrospective analysis of difficult-to-reproduce problems involves puzzling over trace files and testing hypothesis, and when the trace system itself is occasionally unreliable, the set of hypothesis to consider grows. I've tried to keep the amount of kernel infrastructure needed to support this precision and reliability to a minimum, pushing most of the complexity to userspace. But we do need, from the kernel, reliable process disambiguation.

Besides: things like checkpoint and restart are also non-core features, but the kernel has plenty of infrastructure to support them. We're talking about a very lightweight feature in this thread.

Quoted 2 lines

Which userspace tools will be using pid_gen? Are the developers of those tools signed up to use pid_gen?

I'll be changing Android tracing tools to capture process snapshots using pid_gen, using the algorithm in the commit message.

Quoted 5 lines

Quoted 5 lines

kernel/pid.c +5 -0

+u64 read_pid_generation(struct pid_namespace *ns)
+{
+     u64 generation;
+
+

Quoted 8 lines

kernel/pid.c struct pid *alloc_pid(struct pid_namespace *ns) · line 261

Quoted 5 lines

kernel/pid.c +5 -0

+     spin_lock_irq(&pidmap_lock);
+     generation = ns->generation;
+     spin_unlock_irq(&pidmap_lock);
+     return generation;
+}

What is the spinlocking in here for? afaict the only purpose it serves is to make the 64-bit read atomic, so it isn't needed on 32-bit?

ITYM the spinlock is necessary *only* on 32-bit, since 64-bit architectures have atomic 64-bit reads, and 64-bit reads on 32-bit architectures can tear. This function isn't a particularly hot path, so I thought consistency across architectures would be more valuable than avoiding the lock on some systems.

Quoted 45 lines · On Wed, 21 Nov 2018 14:40:28 -0800 Daniel Colascione <[email protected]> wrote:

Quoted 23 lines · Andrew Morton

Quoted 20 lines · On Wed, 21 Nov 2018 12:54:20 -0800 Daniel Colascione <[email protected]> wrote:

Trace analysis code needs a coherent picture of the set of processes and threads running on a system. While it's possible to enumerate all tasks via /proc, this enumeration is not atomic. If PID numbering rolls over during snapshot collection, the resulting snapshot of the process and thread state of the system may be incoherent, confusing trace analysis tools. The fundamental problem is that if a PID is reused during a userspace scan of /proc, it's impossible to tell, in post-processing, whether a fact that the userspace /proc scanner reports regarding a given PID refers to the old or new task named by that PID, as the scan of that PID may or may not have occurred before the PID reuse, and there's no way to "stamp" a fact read from the kernel with a trace timestamp.

This change adds a per-pid-namespace 64-bit generation number, incremented on PID rollover, and exposes it via a new proc file /proc/pid_gen. By examining this file before and after /proc enumeration, user code can detect the potential reuse of a PID and restart the task enumeration process, repeating until it gets a coherent snapshot.

Quoted 6 lines

Quoted 2 lines

PID rollover ought to be rare, so in practice, scan repetitions will be rare.

In general, tracing is a rather specialized thing. Why is this very occasional confusion a sufficiently serious problem to warrant addition of this code?

I wouldn't call tracing a specialized thing: it's important enough to justify its own summit and a whole ecosystem of trace collection and analysis tools. We use it in every day in Android. It's tremendously helpful for understanding system behavior, especially in cases where multiple components interact in ways that we can't readily predict or replicate. Reliability and precision in this area are essential:
retrospective analysis of difficult-to-reproduce problems involves puzzling over trace files and testing hypothesis, and when the trace system itself is occasionally unreliable, the set of hypothesis to consider grows. I've tried to keep the amount of kernel infrastructure needed to support this precision and reliability to a minimum, pushing most of the complexity to userspace. But we do need, from the kernel, reliable process disambiguation.

Quoted 3 lines

Besides: things like checkpoint and restart are also non-core features, but the kernel has plenty of infrastructure to support them. We're talking about a very lightweight feature in this thread.

I'm still not understanding the seriousness of the problem. Presumably you've hit problems in real-life which were serious and frequent enough to justify getting down and writing the code. Please share some sob stories with us!

Quoted 5 lines

Quoted 2 lines

Which userspace tools will be using pid_gen? Are the developers of those tools signed up to use pid_gen?

I'll be changing Android tracing tools to capture process snapshots using pid_gen, using the algorithm in the commit message.

Which other tools could use this and what was the feedback from their developers?

Those people are the intended audience and the best-positioned reviewers so let's hear from them?

Quoted 50 lines · Andrew Morton

Quoted 48 lines · On Wed, 21 Nov 2018 14:40:28 -0800 Daniel Colascione <[email protected]> wrote:

Quoted 25 lines · Andrew Morton

Quoted 23 lines · On Wed, 21 Nov 2018 12:54:20 -0800 Daniel Colascione <[email protected]> wrote:

Trace analysis code needs a coherent picture of the set of processes and threads running on a system. While it's possible to enumerate all tasks via /proc, this enumeration is not atomic. If PID numbering rolls over during snapshot collection, the resulting snapshot of the process and thread state of the system may be incoherent, confusing trace analysis tools. The fundamental problem is that if a PID is reused during a userspace scan of /proc, it's impossible to tell, in post-processing, whether a fact that the userspace /proc scanner reports regarding a given PID refers to the old or new task named by that PID, as the scan of that PID may or may not have occurred before the PID reuse, and there's no way to "stamp" a fact read from the kernel with a trace timestamp.

This change adds a per-pid-namespace 64-bit generation number, incremented on PID rollover, and exposes it via a new proc file /proc/pid_gen. By examining this file before and after /proc enumeration, user code can detect the potential reuse of a PID and restart the task enumeration process, repeating until it gets a coherent snapshot.

Quoted 6 lines

Quoted 2 lines

PID rollover ought to be rare, so in practice, scan repetitions will be rare.

In general, tracing is a rather specialized thing. Why is this very occasional confusion a sufficiently serious problem to warrant addition of this code?

I wouldn't call tracing a specialized thing: it's important enough to justify its own summit and a whole ecosystem of trace collection and analysis tools. We use it in every day in Android. It's tremendously helpful for understanding system behavior, especially in cases where multiple components interact in ways that we can't readily predict or replicate. Reliability and precision in this area are essential:
retrospective analysis of difficult-to-reproduce problems involves puzzling over trace files and testing hypothesis, and when the trace system itself is occasionally unreliable, the set of hypothesis to consider grows. I've tried to keep the amount of kernel infrastructure needed to support this precision and reliability to a minimum, pushing most of the complexity to userspace. But we do need, from the kernel, reliable process disambiguation.

Quoted 8 lines

Quoted 3 lines

Besides: things like checkpoint and restart are also non-core features, but the kernel has plenty of infrastructure to support them. We're talking about a very lightweight feature in this thread.

I'm still not understanding the seriousness of the problem. Presumably you've hit problems in real-life which were serious and frequent enough to justify getting down and writing the code. Please share some sob stories with us!

The problem here is the possibility of confusion, even if it's rare. Does the naive approach of just walking /proc and ignoring the possibility of PID reuse races work most of the time? Sure. But "most of the time" isn't good enough. It's not that there are tons of sob
stories: it's that without completely robust reporting, we can't rule out of the possibility that weirdness we observe in a given trace is actually just an artifact from a kinda-sort-working best-effort trace collection system instead of a real anomaly in behavior. Tracing, essentially, gives us deltas for system state, and without an accurate baseline, collected via some kind of scan on trace startup, it's impossible to use these deltas to robustly reconstruct total system state at a given time. And this matters, because errors in reconstruction (e.g., assigning a thread to the wrong process because the IDs happen to be reused) can affect processing of the whole trace. If it's 3am and I'm analyzing the lone trace from a dogfooder demonstrating a particularly nasty problem, I don't want to find out that the trace I'm analyzing ended up being useless because the kernel's trace system is merely best effort. It's very cheap to be 100% reliable here, so let's be reliable and rule out sources of error.

Quoted 8 lines

Quoted 5 lines

Quoted 2 lines

Which userspace tools will be using pid_gen? Are the developers of those tools signed up to use pid_gen?

I'll be changing Android tracing tools to capture process snapshots using pid_gen, using the algorithm in the commit message.

Which other tools could use this and what was the feedback from their developers?

I'm going to have Android's systrace and Perfetto use this approach. Exactly how many tools signed up to use this feature do you need?

Quoted 2 lines

Those people are the intended audience and the best-positioned reviewers so let's hear from them?

I'm writing plenty of trace analysis tools myself, so I'm part of this intended audience. Other tracing tool authors have told me about out-of-tree hacks for process atomic snapshots via ftrace events. This approach avoids the necessity of these more-invasive hacks.

Quoted 96 lines · Daniel Colascione

Quoted 50 lines · Andrew Morton

Quoted 48 lines · On Wed, 21 Nov 2018 14:40:28 -0800 Daniel Colascione <[email protected]> wrote:

Quoted 25 lines · Andrew Morton

Quoted 23 lines · On Wed, 21 Nov 2018 12:54:20 -0800 Daniel Colascione <[email protected]> wrote:

Trace analysis code needs a coherent picture of the set of processes and threads running on a system. While it's possible to enumerate all tasks via /proc, this enumeration is not atomic. If PID numbering rolls over during snapshot collection, the resulting snapshot of the process and thread state of the system may be incoherent, confusing trace analysis tools. The fundamental problem is that if a PID is reused during a userspace scan of /proc, it's impossible to tell, in post-processing, whether a fact that the userspace /proc scanner reports regarding a given PID refers to the old or new task named by that PID, as the scan of that PID may or may not have occurred before the PID reuse, and there's no way to "stamp" a fact read from the kernel with a trace timestamp.

This change adds a per-pid-namespace 64-bit generation number, incremented on PID rollover, and exposes it via a new proc file /proc/pid_gen. By examining this file before and after /proc enumeration, user code can detect the potential reuse of a PID and restart the task enumeration process, repeating until it gets a coherent snapshot.

Quoted 6 lines

Quoted 2 lines

PID rollover ought to be rare, so in practice, scan repetitions will be rare.

In general, tracing is a rather specialized thing. Why is this very occasional confusion a sufficiently serious problem to warrant addition of this code?

I wouldn't call tracing a specialized thing: it's important enough to justify its own summit and a whole ecosystem of trace collection and analysis tools. We use it in every day in Android. It's tremendously helpful for understanding system behavior, especially in cases where multiple components interact in ways that we can't readily predict or replicate. Reliability and precision in this area are essential:
retrospective analysis of difficult-to-reproduce problems involves puzzling over trace files and testing hypothesis, and when the trace system itself is occasionally unreliable, the set of hypothesis to consider grows. I've tried to keep the amount of kernel infrastructure needed to support this precision and reliability to a minimum, pushing most of the complexity to userspace. But we do need, from the kernel, reliable process disambiguation.

Quoted 8 lines

Quoted 3 lines

Besides: things like checkpoint and restart are also non-core features, but the kernel has plenty of infrastructure to support them. We're talking about a very lightweight feature in this thread.

I'm still not understanding the seriousness of the problem. Presumably you've hit problems in real-life which were serious and frequent enough to justify getting down and writing the code. Please share some sob stories with us!

The problem here is the possibility of confusion, even if it's rare. Does the naive approach of just walking /proc and ignoring the possibility of PID reuse races work most of the time? Sure. But "most of the time" isn't good enough. It's not that there are tons of sob
stories: it's that without completely robust reporting, we can't rule out of the possibility that weirdness we observe in a given trace is actually just an artifact from a kinda-sort-working best-effort trace collection system instead of a real anomaly in behavior. Tracing, essentially, gives us deltas for system state, and without an accurate baseline, collected via some kind of scan on trace startup, it's impossible to use these deltas to robustly reconstruct total system state at a given time. And this matters, because errors in reconstruction (e.g., assigning a thread to the wrong process because the IDs happen to be reused) can affect processing of the whole trace. If it's 3am and I'm analyzing the lone trace from a dogfooder demonstrating a particularly nasty problem, I don't want to find out that the trace I'm analyzing ended up being useless because the kernel's trace system is merely best effort. It's very cheap to be 100% reliable here, so let's be reliable and rule out sources of error.

Quoted 8 lines

Quoted 5 lines

Quoted 2 lines

Which userspace tools will be using pid_gen? Are the developers of those tools signed up to use pid_gen?

I'll be changing Android tracing tools to capture process snapshots using pid_gen, using the algorithm in the commit message.

Which other tools could use this and what was the feedback from their developers?

I'm going to have Android's systrace and Perfetto use this approach. Exactly how many tools signed up to use this feature do you need?

Quoted 2 lines

Those people are the intended audience and the best-positioned reviewers so let's hear from them?

Quoted 4 lines

I'm writing plenty of trace analysis tools myself, so I'm part of this intended audience. Other tracing tool authors have told me about out-of-tree hacks for process atomic snapshots via ftrace events. This approach avoids the necessity of these more-invasive hacks.

Would a tracepoint for pid reuse solve your problem?

Quoted 7 lines

I'm going to have Android's systrace and Perfetto use this approach. Exactly how many tools signed up to use this feature do you need?

Quoted 2 lines

Those people are the intended audience and the best-positioned reviewers so let's hear from them?

Quoted 4 lines

I'm writing plenty of trace analysis tools myself, so I'm part of this intended audience. Other tracing tool authors have told me about out-of-tree hacks for process atomic snapshots via ftrace events. This approach avoids the necessity of these more-invasive hacks.

Would a tracepoint for pid reuse solve your problem?

Quoted 4 lines · Andrew Morton

Quoted 1 line · On Wed, 21 Nov 2018 14:40:28 -0800 Daniel Colascione <[email protected]> wrote:

On Wed, Nov 21, 2018 at 2:12 PM Andrew Morton <[email protected]> wrote:

...

Quoted 14 lines

Quoted 14 lines

I wouldn't call tracing a specialized thing: it's important enough to justify its own summit and a whole ecosystem of trace collection and analysis tools. We use it in every day in Android. It's tremendously helpful for understanding system behavior, especially in cases where multiple components interact in ways that we can't readily predict or replicate. Reliability and precision in this area are essential:
retrospective analysis of difficult-to-reproduce problems involves puzzling over trace files and testing hypothesis, and when the trace system itself is occasionally unreliable, the set of hypothesis to consider grows. I've tried to keep the amount of kernel infrastructure needed to support this precision and reliability to a minimum, pushing most of the complexity to userspace. But we do need, from the kernel, reliable process disambiguation.

Quoted 8 lines

Quoted 3 lines

Besides: things like checkpoint and restart are also non-core features, but the kernel has plenty of infrastructure to support them. We're talking about a very lightweight feature in this thread.

I'm still not understanding the seriousness of the problem. Presumably you've hit problems in real-life which were serious and frequent enough to justify getting down and writing the code. Please share some sob stories with us!

The problem here is the possibility of confusion, even if it's rare. Does the naive approach of just walking /proc and ignoring the possibility of PID reuse races work most of the time? Sure. But "most of the time" isn't good enough. It's not that there are tons of sob
stories: it's that without completely robust reporting, we can't rule out of the possibility that weirdness we observe in a given trace is actually just an artifact from a kinda-sort-working best-effort trace collection system instead of a real anomaly in behavior. Tracing, essentially, gives us deltas for system state, and without an accurate baseline, collected via some kind of scan on trace startup, it's impossible to use these deltas to robustly reconstruct total system state at a given time. And this matters, because errors in

reconstruction (e.g., assigning a thread to the wrong process because the IDs happen to be reused) can affect processing of the whole trace. If it's 3am and I'm analyzing the lone trace from a dogfooder demonstrating a particularly nasty problem, I don't want to find out that the trace I'm analyzing ended up being useless because the kernel's trace system is merely best effort. It's very cheap to be 100% reliable here, so let's be reliable and rule out sources of error.

Quoted 8 lines

Quoted 5 lines

Quoted 2 lines

Which userspace tools will be using pid_gen? Are the developers of those tools signed up to use pid_gen?

I'll be changing Android tracing tools to capture process snapshots using pid_gen, using the algorithm in the commit message.

Which other tools could use this and what was the feedback from their developers?

I'm going to have Android's systrace and Perfetto use this approach. Exactly how many tools signed up to use this feature do you need?

Quoted 2 lines

Those people are the intended audience and the best-positioned reviewers so let's hear from them?

I'm writing plenty of trace analysis tools myself, so I'm part of this intended audience. Other tracing tool authors have told me about out-of-tree hacks for process atomic snapshots via ftrace events. This approach avoids the necessity of these more-invasive hacks.

Quoted 43 lines · On Wed, 21 Nov 2018 15:21:40 -0800 Daniel Colascione <[email protected]> wrote:

Quoted 4 lines · Andrew Morton

Quoted 1 line · On Wed, 21 Nov 2018 14:40:28 -0800 Daniel Colascione <[email protected]> wrote:

On Wed, Nov 21, 2018 at 2:12 PM Andrew Morton <[email protected]> wrote:

...

Quoted 14 lines

Quoted 14 lines

I wouldn't call tracing a specialized thing: it's important enough to justify its own summit and a whole ecosystem of trace collection and analysis tools. We use it in every day in Android. It's tremendously helpful for understanding system behavior, especially in cases where multiple components interact in ways that we can't readily predict or replicate. Reliability and precision in this area are essential:
retrospective analysis of difficult-to-reproduce problems involves puzzling over trace files and testing hypothesis, and when the trace system itself is occasionally unreliable, the set of hypothesis to consider grows. I've tried to keep the amount of kernel infrastructure needed to support this precision and reliability to a minimum, pushing most of the complexity to userspace. But we do need, from the kernel, reliable process disambiguation.

Quoted 8 lines

Quoted 3 lines

Besides: things like checkpoint and restart are also non-core features, but the kernel has plenty of infrastructure to support them. We're talking about a very lightweight feature in this thread.

I'm still not understanding the seriousness of the problem. Presumably you've hit problems in real-life which were serious and frequent enough to justify getting down and writing the code. Please share some sob stories with us!

The problem here is the possibility of confusion, even if it's rare. Does the naive approach of just walking /proc and ignoring the possibility of PID reuse races work most of the time? Sure. But "most of the time" isn't good enough. It's not that there are tons of sob
stories: it's that without completely robust reporting, we can't rule out of the possibility that weirdness we observe in a given trace is actually just an artifact from a kinda-sort-working best-effort trace collection system instead of a real anomaly in behavior. Tracing, essentially, gives us deltas for system state, and without an accurate baseline, collected via some kind of scan on trace startup, it's impossible to use these deltas to robustly reconstruct total system state at a given time. And this matters, because errors in

Quoted 8 lines

reconstruction (e.g., assigning a thread to the wrong process because the IDs happen to be reused) can affect processing of the whole trace. If it's 3am and I'm analyzing the lone trace from a dogfooder demonstrating a particularly nasty problem, I don't want to find out that the trace I'm analyzing ended up being useless because the kernel's trace system is merely best effort. It's very cheap to be 100% reliable here, so let's be reliable and rule out sources of error.

So we're solving a problem which isn't known to occur, but solving it provides some peace-of-mind? Sounds thin!

Quoted 55 lines · Andrew Morton

Quoted 43 lines · On Wed, 21 Nov 2018 15:21:40 -0800 Daniel Colascione <[email protected]> wrote:

Quoted 4 lines · Andrew Morton

Quoted 1 line · On Wed, 21 Nov 2018 14:40:28 -0800 Daniel Colascione <[email protected]> wrote:

On Wed, Nov 21, 2018 at 2:12 PM Andrew Morton <[email protected]> wrote:

...

Quoted 14 lines

Quoted 14 lines

I wouldn't call tracing a specialized thing: it's important enough to justify its own summit and a whole ecosystem of trace collection and analysis tools. We use it in every day in Android. It's tremendously helpful for understanding system behavior, especially in cases where multiple components interact in ways that we can't readily predict or replicate. Reliability and precision in this area are essential:
retrospective analysis of difficult-to-reproduce problems involves puzzling over trace files and testing hypothesis, and when the trace system itself is occasionally unreliable, the set of hypothesis to consider grows. I've tried to keep the amount of kernel infrastructure needed to support this precision and reliability to a minimum, pushing most of the complexity to userspace. But we do need, from the kernel, reliable process disambiguation.

Quoted 8 lines

Quoted 3 lines

Besides: things like checkpoint and restart are also non-core features, but the kernel has plenty of infrastructure to support them. We're talking about a very lightweight feature in this thread.

I'm still not understanding the seriousness of the problem. Presumably you've hit problems in real-life which were serious and frequent enough to justify getting down and writing the code. Please share some sob stories with us!

The problem here is the possibility of confusion, even if it's rare. Does the naive approach of just walking /proc and ignoring the possibility of PID reuse races work most of the time? Sure. But "most of the time" isn't good enough. It's not that there are tons of sob
stories: it's that without completely robust reporting, we can't rule out of the possibility that weirdness we observe in a given trace is actually just an artifact from a kinda-sort-working best-effort trace collection system instead of a real anomaly in behavior. Tracing, essentially, gives us deltas for system state, and without an accurate baseline, collected via some kind of scan on trace startup, it's impossible to use these deltas to robustly reconstruct total system state at a given time. And this matters, because errors in

Quoted 8 lines

reconstruction (e.g., assigning a thread to the wrong process because the IDs happen to be reused) can affect processing of the whole trace. If it's 3am and I'm analyzing the lone trace from a dogfooder demonstrating a particularly nasty problem, I don't want to find out that the trace I'm analyzing ended up being useless because the kernel's trace system is merely best effort. It's very cheap to be 100% reliable here, so let's be reliable and rule out sources of error.

Quoted 2 lines

So we're solving a problem which isn't known to occur, but solving it provides some peace-of-mind? Sounds thin!

So you want to reject a cheap fix for a problem that you know occurs at some non-zero frequency? There's a big difference between "may or may not occur" and "will occur eventually, given enough time, and so must be taken into account in analysis". Would you fix a refcount race that you knew was possible, but didn't observe? What, exactly, is your threshold for accepting a fix that makes tracing more reliable?

Quoted 14 lines

Quoted 14 lines

Quoted 14 lines

The problem here is the possibility of confusion, even if it's rare. Does the naive approach of just walking /proc and ignoring the possibility of PID reuse races work most of the time? Sure. But "most of the time" isn't good enough. It's not that there are tons of sob
stories: it's that without completely robust reporting, we can't rule out of the possibility that weirdness we observe in a given trace is actually just an artifact from a kinda-sort-working best-effort trace collection system instead of a real anomaly in behavior. Tracing, essentially, gives us deltas for system state, and without an accurate baseline, collected via some kind of scan on trace startup, it's impossible to use these deltas to robustly reconstruct total system state at a given time. And this matters, because errors in reconstruction (e.g., assigning a thread to the wrong process because

Quoted 8 lines

Quoted 8 lines

Quoted 7 lines

the IDs happen to be reused) can affect processing of the whole trace. If it's 3am and I'm analyzing the lone trace from a dogfooder demonstrating a particularly nasty problem, I don't want to find out that the trace I'm analyzing ended up being useless because the kernel's trace system is merely best effort. It's very cheap to be 100% reliable here, so let's be reliable and rule out sources of error.

Quoted 21 lines

Quoted 12 lines

The problem here is the possibility of confusion, even if it's rare. Does the naive approach of just walking /proc and ignoring the possibility of PID reuse races work most of the time? Sure. But "most of the time" isn't good enough. It's not that there are tons of sob
stories: it's that without completely robust reporting, we can't rule out of the possibility that weirdness we observe in a given trace is actually just an artifact from a kinda-sort-working best-effort trace collection system instead of a real anomaly in behavior. Tracing, essentially, gives us deltas for system state, and without an accurate baseline, collected via some kind of scan on trace startup, it's impossible to use these deltas to robustly reconstruct total system state at a given time. And this matters, because errors in

Quoted 8 lines

reconstruction (e.g., assigning a thread to the wrong process because the IDs happen to be reused) can affect processing of the whole trace. If it's 3am and I'm analyzing the lone trace from a dogfooder demonstrating a particularly nasty problem, I don't want to find out that the trace I'm analyzing ended up being useless because the kernel's trace system is merely best effort. It's very cheap to be 100% reliable here, so let's be reliable and rule out sources of error.

Quoted 2 lines

So we're solving a problem which isn't known to occur, but solving it provides some peace-of-mind? Sounds thin!

So you want to reject a cheap fix for a problem that you know occurs at some non-zero frequency? There's a big difference between "may or may not occur" and "will occur eventually, given enough time, and so must be taken into account in analysis". Would you fix a refcount race that you knew was possible, but didn't observe? What, exactly, is your threshold for accepting a fix that makes tracing more reliable?

Quoted 24 lines · On Wed, 21 Nov 2018 16:28:56 -0800 Daniel Colascione <[email protected]> wrote:

Quoted 21 lines

Quoted 12 lines

The problem here is the possibility of confusion, even if it's rare. Does the naive approach of just walking /proc and ignoring the possibility of PID reuse races work most of the time? Sure. But "most of the time" isn't good enough. It's not that there are tons of sob
stories: it's that without completely robust reporting, we can't rule out of the possibility that weirdness we observe in a given trace is actually just an artifact from a kinda-sort-working best-effort trace collection system instead of a real anomaly in behavior. Tracing, essentially, gives us deltas for system state, and without an accurate baseline, collected via some kind of scan on trace startup, it's impossible to use these deltas to robustly reconstruct total system state at a given time. And this matters, because errors in

Quoted 8 lines

reconstruction (e.g., assigning a thread to the wrong process because the IDs happen to be reused) can affect processing of the whole trace. If it's 3am and I'm analyzing the lone trace from a dogfooder demonstrating a particularly nasty problem, I don't want to find out that the trace I'm analyzing ended up being useless because the kernel's trace system is merely best effort. It's very cheap to be 100% reliable here, so let's be reliable and rule out sources of error.

Quoted 2 lines

So we're solving a problem which isn't known to occur, but solving it provides some peace-of-mind? Sounds thin!

Quoted 6 lines

So you want to reject a cheap fix for a problem that you know occurs at some non-zero frequency? There's a big difference between "may or may not occur" and "will occur eventually, given enough time, and so must be taken into account in analysis". Would you fix a refcount race that you knew was possible, but didn't observe? What, exactly, is your threshold for accepting a fix that makes tracing more reliable?

Well for a start I'm looking for a complete patch changelog. One which permits readers to fully understand the user-visible impact of the problem.

If it is revealed that is a theoretical problem which has negligible end-user impact then sure, it is rational to leave things as they are. That's what "negligible" means!

Have you done much
retrospective long trace analysis?

The patch already describes the problem, the solution, and the way in which this solution is provided. What more information do you want?

Quoted 2 lines · On Wed, 21 Nov 2018 17:08:08 -0800 Daniel Colascione <[email protected]> wrote:

Have you done much
retrospective long trace analysis?

No. Have you?

Of course you have, which is why I and others are dependent upon you to explain why this change is worth adding to Linux. If this thing solves a problem which we expect will not occur for anyone between now and the heat death of the universe then this impacts our decisions.

Quoted 6 lines · Andrew Morton

Quoted 2 lines · On Wed, 21 Nov 2018 17:08:08 -0800 Daniel Colascione <[email protected]> wrote:

Have you done much
retrospective long trace analysis?

Quoted 6 lines

No. Have you?

Of course you have, which is why I and others are dependent upon you to explain why this change is worth adding to Linux. If this thing solves a problem which we expect will not occur for anyone between now and the heat death of the universe then this impacts our decisions.

I use ftrace the most on Android, so let me take a shot.

In addition to the normal "debug a slow thing" use cases for ftrace, Android has started exploring two other ways of using ftrace:

1. "Flight recorder" mode: trigger ftrace for some amount of time when a particular anomaly is detected to make debugging those cases easier.

2. Long traces: let a trace stream to disk for hours or days, then postprocess it to get some deeper insights about system behavior. We've used this very successfully to debug and optimize power consumption.

Knowing the initial state of the system is a pain for both of these cases. For example, one of the things I'd like to know in some of my current use cases for long traces is the current oom_score_adj of every process in the system, but similar to PID reuse, that can change very quickly due to userspace behavior. There's also a race between reading that value in userspace and writing it to trace_marker:

1. Userspace daemon X reads oom_score_adj for a process Y.
2. Process Y gets a new oom_score_adj value, triggering the oom/oom_score_adj_update tracepoint.
3. Daemon X writes the old oom_score_adj value to trace_marker.

As I was writing this, though, I realized that the race doesn't matter so long as our tools follow the same basic practice (for PID reuse, oom_score_adj, or anything else we need):

1. Daemon enables all requested tracepoints and resets the trace clock.
2. Daemon enables tracing
3. Daemon dumps initial state for any tracepoint we care about.
4. When postprocessing, a tool must consider the initial state of a value (eg, oom_score_adj of pid X) to be either the initial state as reported by the daemon or the first ftrace event reporting that value. If there is an ftrace event in the trace before the report from the daemon, the report from the daemon should be ignored.

This change adds a per-pid-namespace 64-bit generation number, incremented on PID rollover, and exposes it via a new proc file /proc/pid_generation. By examining this file before and after /proc enumeration, user code can detect the potential reuse of a PID and restart the task enumeration process, repeating until it gets a coherent snapshot.

Sent: 22 November 2018 11:20

Quoted 6 lines · Daniel Colascione

This change adds a per-pid-namespace 64-bit generation number, incremented on PID rollover, and exposes it via a new proc file /proc/pid_generation. By examining this file before and after /proc enumeration, user code can detect the potential reuse of a PID and restart the task enumeration process, repeating until it gets a coherent snapshot.

I see downthread this patch has been withdrawn, but nonetheless I'm still curious - does this actually solve the problem?

It seems to me that a PID could be reused within a scan even if the generation number remains the same at the beginning and end of a scan:

From: Kevin Easton

Quoted 13 lines

Sent: 22 November 2018 11:20

Quoted 6 lines · Daniel Colascione

This change adds a per-pid-namespace 64-bit generation number, incremented on PID rollover, and exposes it via a new proc file /proc/pid_generation. By examining this file before and after /proc enumeration, user code can detect the potential reuse of a PID and restart the task enumeration process, repeating until it gets a coherent snapshot.

I see downthread this patch has been withdrawn, but nonetheless I'm still curious - does this actually solve the problem?

Quoted 2 lines

It seems to me that a PID could be reused within a scan even if the generation number remains the same at the beginning and end of a scan:

Why not allocate a 48bit generation number to each 16bit pid? Then you have a 64bit 'extended-pid' that can be assumed to never be reused. Provided enough interfaces are enhanced to support 'extended-pid' values you'll never get reused values.