2,257
edits
Changes
no edit summary
[http://man7.org/linux/man-pages/man3/strcmp.3.html strcmp] call. This allows CRIU to track resources with a sorting algorithm.
[http://man7.org/linux/man-pages/man3/strcmp.3.html strcmp] call. This allows CRIU to track resources with a sorting algorithm.
=== Kcmp-trees ===
=== API ===
CRIU gather files, filesystems, vitrual memory descriptors, signal handlers and file descriptors associated with a process
CRIU gather files, filesystems, vitrual memory descriptors, signal handlers and file descriptors associated with a process
Each tree internally represented as [http://en.wikipedia.org/wiki/Red%E2%80%93black_tree red-black] tree.
Each tree internally represented as [http://en.wikipedia.org/wiki/Red%E2%80%93black_tree red-black] tree.
When CRIU gathers process resources it check if a resource is already sitting inside of a tree calling
When CRIU gathers process resources it check if a resource is already sitting inside of a tree calling
two processes might share a lot of resources and dumping them multiple times would cause very serious
two processes might share a lot of resources and dumping them multiple times would cause very serious
performance issue.
performance issue.
=== Two trees ===
In order to minimize the number of <code>kcmp</code> calls we use two IDs for an object -- so called ''gen_id'' and the ''ID'' itself.
The gen_id is and ID that is created based on some visible attributes of an object. E.g. for a file it's generated out of the inode number, device and position. Having two gen_id-s different we can say that the objects differ to. E.g. file with different inodes are different. But two equal gen_id-s may refer to different files too. So to check ''this'' we call <code>kcmp</code>.
For faster lookup we store objects in two trees. First RB-tree is the sorted by gen_id-s tree. When we fail to find an element in a tree we assume that the object we check is the new one. When we ''find'' an element in the tree we need to go on and call <code>kcmp</code>. But since one gen_id leaf may refer to several elements ''and'' kernel reports equals/greater/less from <code>kcmp</code> we create the 2nd tree under the gen_id leaf -- the sorted by ID tree where the comparison function is the <code>kcmp</code>.
[[Category: Under the hood]]
[[Category: Under the hood]]