Restorer v2

The current way of restoring from images is quite straightforward -- we just fork the necessary amount of tasks, then each of them starts "dressing" itself based on the data from image files. Sometimes shared resources appear, e.g. files inherited or sessions inherited on fork, or CLONE_XXX objects. With these we write code, that handles only this type of resources -- files a sent to co-owners via unix sockets, CLONE_XXX stuff is pre-created on fork stage. Sometimes more interesting dependencies arise, for example -- invisible files. These are also special-cared.

All this is not nice. We believe, that the restoring process can (and should) look better. Like this.

Concept

The result that we want to achieve can be described as a graph of objects, each edge of it having a special "relationship" meaning. This graph should be generated using a set of pre-defined rules, e.g.

fork() -- an object type "task" may create a copy of itself, each "linked" node of this graph get "linked" to the new object
open() -- a new object type "file" appear in a graph "linked" to the "task" object doing open()

And so on.

Another way of describing the thing is -- a string of sequences like {o,t,[l]*} where o is an ID of an object, t is its type, [l]* is an array of links to another objects. The generation rules can look like

fork() — ({(*),task,[(*)]}) -> \1,{$new,task,([parent=\2,\3])} which means that any task can create a copy of itself having it as parent (link) and the rest of objects shared
open() — {(*),task,(*)} -> {\1,task,[file=$new,\2]},{$new,file,[]} which means that any task can create a new object of type file linked to it

The restoring process then is: given a final graph or string and the set of generating rules find out what sequence of the latter can produce the former.

This task (in its 2nd description) reminds the task of solving the context-sensitive grammar.

Examples

Process tree, sessions and groups

In case of three IDs only we can define a task as a non-terminal looking like {PGS[Ki]} where P is task PID, G is task PGID, S is task Session ID and [Ki] is the list of children.

Initial tree would look like

{111\nil}

and the rules would look like below.

FORK:       {T(..)(.*)}                  -> {T\1N\2}|{N\1}     // T forks N
EXIT:       {I(..)(.*)}(.*){X(..)(.*)}   -> {I\1\2\5}\3        // X exits and all its kids are reparented to I (init)
SETSID:     {S(.)(.*)}                   -> {SS\1}             // S becomes a new session leader
SETPGID(0): {P(.)(.)(.*)}                -> {P\1P\3}           // P becomes a new group leader
SETPGID(G): {G(.)G(.*)}(.*){P(.)(.)(.*)} -> {G\1G\2}\3{P\4G\6} // P joins session of alive G