Changes

1,026 bytes added ,  20:53, 5 March 2015
no edit summary
Line 8: Line 8:  
[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
Line 17: Line 17:     
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.
  −
=== Requesting new ID ===
      
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
Line 28: Line 26:  
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]]