The best kittens, technology, and video games blog in the world.

Monday, April 05, 2010

How to kill all your children

Félinitude-I by Etolane from flickr (CC-NC-ND)

I'm sure you all had this problem a few times - you tell your children to do something, and they just won't obey. At first you wait, but your patience grows thin until you come to face the inevitable - you have no choice but to kill all you children. But first you need to find them.

Unfortunately there's no portable API for traversing process tree to find all your descendant processes. ps, pstree and similar programs use operating system-specific hacks, like reading procfs (Linux) or reading tea leave patterns (OSX). Even command line options for ps seem to follow three different mutually incompatible systems. And careful tracking of return values of fork won't do you any good, as forked processes might have kept spawning.

So we'll need more than one line of Ruby. Maybe even as many as five!

First, let's get raw data out of the operating system. If it was Linux-only exercise, procps would work fine, but some experimentation shows that both Linux and OSX versions of ps support -eo pid,ppid options for getting process parentage graph.


$ ps -eo pid,ppid
  PID  PPID
    1     0
   10     1
   11     1
   12     1
   14     1
    ... 
 3367  3366
 3382  3367
 3441  1240
 3442  3441
 3460  3442


Before doing anything else, let's just turn it into a hash.


Hash[*`ps -eo pid,ppid`.scan(/\d+/).map{|x|x.to_i}]

Now we know what's parent of every process and the only problem is reverting this graph - something that's strangely missing from the usual Hash/Array toolkit that Ruby and Perl are based upon.

A brief pause time. You might be wondering what happens when process's parent dies. Normally it is the reparented to its grandparent, or init process, whichever is more sensible based on process groups and other things we don't need to concern ourselves with. So process graph is always proper, unless something weird happened during execution of ps (atomicity in my Unix? it's less likely than you think).

Now it's time to do a lazy half-unification. Create a list for every process containing just its id, and then go through all processes and add reference to its list to its parents' list. When we're done every process's list will contain at some depth ids of all its descendants. Now it's just flatten and remove yourself from the list to avoid a suicide.


def Process.descendant_processes(base=Process.pid)
  descendants = Hash.new{|ht,k| ht[k]=[k]}
  Hash[*`ps -eo pid,ppid`.scan(/\d+/).map{|x|x.to_i}].each{|pid,ppid|
    descendants[ppid] << descendants[pid]
  }
  descendants[base].flatten - [base]
end

Once you've found all your children and further descendants, it's just a matter of a quick kill -9 to finish them all off.

Death Sentence - Help Roni - California by fofurasfelinas from flickr (CC-NC-ND)


As a bonus, here's the version of the same function in Perl.

sub flatten {
  map{ (ref($_) eq "ARRAY") ? map{flatten($_)}@$_ : $_ } @_;
}
sub descendant_processes {
  my ($base) = (@_, $$);
  my %parentage = (`ps -eo pid,ppid` =~ /\d+/g);
  my %reverse = map { ($_, [$_]) } %parentage;
  while (($pid,$ppid) = each %parentage){
    push @{$reverse{$ppid}}, $reverse{$pid};
  }
  shift @{$reverse{$base}};
  flatten($reverse{$base});
}


Notice the advantage Ruby has over Perl - and how workaround while annoying are not that difficult:
  • There are no default arguments, but we can easily hack them with an equivalent of [*arguments, default] for one-argument functions.
  • I wanted to say in Perl we don't need to_i - but then it doesn't really change anything in Ruby either, operating on pids like 1234 instead of "1234" just feels saner.
  • We can use Ruby autovivification which takes blocks, but Perl autovivification is useless as we want hash values to default to [key] not []
  • There's no flatten so we need to implement it (and it's such an extremely common function - the reason it's not in Perl is because Perl started without any support for nested arrays whatsoever)
  • There's no way to subtract lists from each other like Ruby's [1,2,3] - [2]. Fortunately we know own pid is always first, so we can just shift the list.
As always, C++ version left as an exercise for the readers.

7 comments:

Anonymous said...

Is the hashtable updated in realtime in Ruby? Basically what I'm asking is what happens if a new child is created after you've created your list of children to kill?

Anonymous said...

t isn't subtraction in ruby, it is set difference. [1,2,2,2,3] - [2] is [1,3] not [1,2,2,3]. This is inconsistent with the normal math operator \ which is usually used for set difference. Even worse it means that + and - are not semantically related at all.

- on lists in ruby is poor design, it is unrelated to +, it is not the inverse of + and can't be used to form anything like a ring.

Ruby should've never overloaded - on lists. Besides hashes are usually used for set operations in perl.

Blair Strang said...

Huh? Why didn't you just save the child PIDs when you forked them?

Anonymous said...

In POSIX-compatible systems, you can also use the kill(2) function to send signals, e.g. SIGTERM, to all processes in the caller's process group. The sender itself would presumably temporarily ignore SIGTERM to avoid committing suicide, unless that's the intent.

Ensuring that your process group only contains your process and its children requires a call to setpgid(2) before the first call to fork(2).

UNIX rarely requires hacks such as given in this blog post.

taw said...

Anonymous: No, but you usually do it when processes hang, not when they're hostile and trying to outrun you. UNIX has no API for realtime information like that.

Anonymous: It's not set difference, it's list subtraction and it's extremely useful and common operation. Subtraction is not inverse of + even on floating point numbers so why does it bother you?

Blair Strang: Because your children forked further, and you want to kill what they've spawned too, and saving child PIDs doesn't help with that at all.

Anonymous: When they hang you must use KILL, which you cannot ignore, so your entire approach fails.

Even if this wasn't a case, setpgid is a stupid hack - if every process called setpgid just in case it might need to kill its uncooperative children, then every process would have different pgid and kill-by-setpgid wouldn't work. It only works if it's used by very few processes, defeating its whole purpose.

What you want is full process tree traversal - but as setpgid hack was easier to implement in C than proper process tree traversal API, that's what they've done. Unix "worse is better".

Unless we had process-group tree traversal API - so we could kill children which also "called setpgid before first fork", but if we had that, why not give us full process tree traversal API?

Blair Strang said...

Yes, the code is elegant, and yep, it'll get the job done (assuming you don't care about races or orphans - which one usually doesn't in a last ditch scenario).

But it's a nice implementation of what is essentially a kludge. If you find yourself needing to do this, there are underlying problems and this is a way to paper over them.

I don't want to sound too critical because yeah, sometimes there's no other way. At least until whoever wrote your child processes gets around to her bug queue ;)

Describing setpgid as a 'stupid hack' ignores the fact that even if a decent API for process tree traversal existed, you couldn't implement what you want without race conditions between enumeration and killing.

taw said...

Blair Strang: As for them fixing their bugs - forget about it, the children in original problem are xulrunner process and whatever nightmares they've spawned.

Can I use setpgid to send KILL signal to everyone but myself? Even better, can I get pid from fork(), and kill just it and all its descendants using setpgid? Oh, actually that might be possible if I called setpgid after fork and before exec and told parent process about that pgid somehow.

So, yes, that's one way - but it would still fail if any of them use setpgid.