Real-life task: How to restore a process tree in Linux

We are developing a CRIU project (Checkpoint / Restore in Userspace) and we had a rather interesting task on how to restore the original process tree. I suggest you try to solve it.

A task


CRIU is a utility that allows you to save the state of processes to disk and resolve them later on this or any other machine. One of the recovery subtasks is to find a sequence of actions in order to restore the process tree. The input contains a set of parameters for each process: a unique identifier (PID), a link to the parent (PPID), a session identifier (SID).

image


Rules by which Linux processes live


  • The Linux process hierarchy has a tree structure.
  • Each process has a unique PID (process ID)
  • Each process has a SID (session ID). It is inherited from the parent, and at any time, the process can decide to become a leader, after which its SID will be equal to the PID.
  • If the process dies, then all its child processes move to the nearest ancestor, which is the child-reaper, and the process itself goes into the "zombie" state.
  • A parent can pick up (destroy) any of the daughter zombies.
  • The root process is always child-reaper, the rest are optional (they can turn this functionality on and off at any time).
  • Processes can be born not only down (to become a daughter), but also to the side (become a brother).


Teams:


  • fork (pid) - creates a process with the given PID, which will become a child of the current
  • clone (pid, CLONE_PARENT) - a process is created with the given PID, which will become a brother for the current
  • prctl (PR_SET_CHILD_SUBREAPER, flag) - says that the current process will be child-reaper if flag = true and that the current process refuses to be child-reaper if flag = false
  • setsid () - makes the current process the session leader.
  • exit () - the process dies, but does not disappear, but enters the "zombie" state. All his descendants move to the nearest child reaper.
  • wait (pid) - selects (destroys) zombies with the given PID. This operation can only be done by a zombie parent.


Sample input


Input data contains a line for each process. Each line contains 3 numbers pid, ppid (parent pid), sid and zombie flag, which has the value 0 - if the process is dead ("zombie"), and 1 - if the process is alive.

1 0 1 1
6 1 6 1
8 6 7 1
15 6 12 1
10 1 10 1
11 10 7 1
13 10 12 1

Sample output


1: fork (6)
6: fork (7)
7: setsid ()
7: clone (8, CLONE_PARENT)
7: exit ()
6: wait ()
8: fork (9)
9: fork (10)
10: fork (11)
10: fork (12)
12: setsid ()
12: clone (13, CLONE_PARENT)
12: clone (14, CLONE_PARENT)
12: exit ()
10: wait (12)
14: fork (15)
6: prctl (PR_SET_CHILD_SUBREAPER, 1)
14: exit ()
10: wait (14)
6: prctl (PR_SET_CHILD_SUBREAPER, 0) @ A 9: exit () C
8: wait (9)
6: setsid ()
10: setsid ()