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

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 to restore the process tree. Input data contains a set of parameters for each process: a unique identifier (PID), a reference to the parent (PPID), a session identifier (SID).



')

The rules by which live processes in Linux

• 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 may decide to become a leader, after which its SID will be equal to the PID.
• If a process dies, then all its child processes move to the nearest ancestor, who is a child-reaper, and the process itself goes into a zombie state.
• The parent can pick up (destroy) any of the daughter zombies.
• The root process is always a child-reaper, the rest is optional (they can turn this functionality on and off at any time).
• Processes can be born not only down (to become a child), but also to the side (to become a brother).

Commands:

• fork (pid) - creates a process with the specified PID, which will become a child of the current
• clone (pid, CLONE_PARENT) - creates a process with the specified 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 a session leader.
• exit () - the process dies, but does not disappear, but goes into the “zombie” state. All his descendants move to the nearest child-reaper.
• wait (pid) - selects (destroys) zombies with a given PID. This operation can be performed only by a zombie parent.

Sample input

Input data contains a line for each process. Each line contains 3 numbers pid, ppid (parent's pid), sid and zombie flag, which is 0 - if the process is dead (zombies), and 1 - if the process is live.

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)
9: exit ()
8: wait (9)
6: setsid ()
10: setsid ()