LCOV - code coverage report
Current view: top level - crtools - kcmp-ids.c (source / functions) Hit Total Coverage
Test: crtools.info Lines: 86 87 98.9 %
Date: 2012-12-28 Functions: 7 7 100.0 %
Branches: 28 36 77.8 %

           Branch data     Line data    Source code
       1                 :            : #include <unistd.h>
       2                 :            : #include <stdlib.h>
       3                 :            : #include "types.h"
       4                 :            : #include "rbtree.h"
       5                 :            : #include "util.h"
       6                 :            : #include "syscall.h"
       7                 :            : #include "kcmp-ids.h"
       8                 :            : 
       9                 :            : /*
      10                 :            :  * We track shared files by global rbtree, where each node might
      11                 :            :  * be a root for subtree. The reason for that is the nature of data
      12                 :            :  * we obtain from operating system.
      13                 :            :  *
      14                 :            :  * Basically OS provides us two ways to distinguish files
      15                 :            :  *
      16                 :            :  *  - information obtained from fstat call
      17                 :            :  *  - shiny new sys_kcmp system call (which may compare the file descriptor
      18                 :            :  *    pointers inside the kernel and provide us order info)
      19                 :            :  *
      20                 :            :  * So, to speedup procedure of searching for shared file descriptors
      21                 :            :  * we use both techniques. From fstat call we get that named general file
      22                 :            :  * IDs (genid) which are carried in the main rbtree.
      23                 :            :  *
      24                 :            :  * In case if two genid are the same -- we need to use a second way and
      25                 :            :  * call for sys_kcmp. Thus, if kernel tells us that files have identical
      26                 :            :  * genid but in real they are different from kernel point of view -- we assign
      27                 :            :  * a second unique key (subid) to such file descriptor and put it into a subtree.
      28                 :            :  *
      29                 :            :  * So the tree will look like
      30                 :            :  *
      31                 :            :  *               (root)
      32                 :            :  *               genid-1
      33                 :            :  *              /    \
      34                 :            :  *         genid-2  genid-3
      35                 :            :  *            / \    / \
      36                 :            :  *
      37                 :            :  * Where each genid node might be a sub-rbtree as well
      38                 :            :  *
      39                 :            :  *               (genid-N)
      40                 :            :  *               /      \
      41                 :            :  *           subid-1   subid-2
      42                 :            :  *            / \       / \
      43                 :            :  *
      44                 :            :  * Carrying two rbtree at once allow us to minimize the number
      45                 :            :  * of sys_kcmp syscalls, also to collect and dump file descriptors
      46                 :            :  * in one pass.
      47                 :            :  */
      48                 :            : 
      49                 :            : struct kid_entry {
      50                 :            :         struct rb_node  node;
      51                 :            : 
      52                 :            :         struct rb_root  subtree_root;
      53                 :            :         struct rb_node  subtree_node;
      54                 :            : 
      55                 :            :         u32             subid;  /* subid is always unique */
      56                 :            :         struct kid_elem elem;
      57                 :            : } __aligned(sizeof(long));
      58                 :            : 
      59                 :        820 : static void show_subnode(struct rb_node *node, int self)
      60                 :            : {
      61                 :        820 :         struct kid_entry *this = rb_entry(node, struct kid_entry, subtree_node);
      62                 :            : 
      63         [ +  + ]:        820 :         pr_info("\t\t| %#x.%#x %s\n", this->elem.genid, this->subid,
      64                 :            :                         self ? "(self)" : "");
      65         [ +  + ]:        820 :         if (node->rb_left) {
      66                 :          2 :                 pr_info("\t\t| left:\n");
      67                 :          2 :                 show_subnode(node->rb_left, 0);
      68                 :          2 :                 pr_info("\t\t| --l\n");
      69                 :            :         }
      70         [ +  + ]:        820 :         if (node->rb_right) {
      71                 :        149 :                 pr_info("\t\t| right:\n");
      72                 :        149 :                 show_subnode(node->rb_right, 0);
      73                 :        149 :                 pr_info("\t\t| --r\n");
      74                 :            :         }
      75                 :        820 : }
      76                 :            : 
      77                 :        669 : static void show_subtree(struct rb_root *root)
      78                 :            : {
      79                 :        669 :         pr_info("\t\t| SubTree\n");
      80                 :        669 :         show_subnode(root->rb_node, 1);
      81                 :        669 : }
      82                 :            : 
      83                 :        669 : static void show_node(struct rb_node *node)
      84                 :            : {
      85                 :        669 :         struct kid_entry *this = rb_entry(node, struct kid_entry, node);
      86                 :            : 
      87                 :        669 :         pr_info("\t%#x.%#x\n", this->elem.genid, this->subid);
      88         [ +  + ]:        669 :         if (node->rb_left) {
      89                 :        230 :                 pr_info("\tleft:\n");
      90                 :        230 :                 show_node(node->rb_left);
      91                 :        230 :                 pr_info("\t--l\n");
      92                 :            :         }
      93         [ +  + ]:        669 :         if (node->rb_right) {
      94                 :        273 :                 pr_info("\tright:\n");
      95                 :        273 :                 show_node(node->rb_right);
      96                 :        273 :                 pr_info("\t--r\n");
      97                 :            :         }
      98                 :            : 
      99                 :        669 :         show_subtree(&this->subtree_root);
     100                 :        669 :         pr_info("\t--s\n");
     101                 :        669 : }
     102                 :            : 
     103                 :        166 : void kid_show_tree(struct kid_tree *tree)
     104                 :            : {
     105                 :        166 :         struct rb_root *root = &tree->root;
     106                 :            : 
     107                 :        166 :         pr_info("\tTree of %d objects\n", tree->kcmp_type);
     108         [ +  - ]:        166 :         if (root->rb_node)
     109                 :        166 :                 show_node(root->rb_node);
     110                 :        166 : }
     111                 :            : 
     112                 :       2216 : static struct kid_entry *alloc_kid_entry(struct kid_tree *tree, struct kid_elem *elem)
     113                 :            : {
     114                 :            :         struct kid_entry *e;
     115                 :            : 
     116         [ -  + ]:       2216 :         e = xmalloc(sizeof(*e));
     117         [ +  - ]:       2216 :         if (!e)
     118                 :            :                 goto err;
     119                 :            : 
     120                 :       2216 :         e->subid     = tree->subid++;
     121                 :       2216 :         e->elem              = *elem;
     122                 :            : 
     123                 :            :         /* Make sure no overflow here */
     124         [ -  + ]:       2216 :         BUG_ON(!e->subid);
     125                 :            : 
     126                 :       2216 :         rb_init_node(&e->node);
     127                 :       2216 :         rb_init_node(&e->subtree_node);
     128                 :       2216 :         e->subtree_root = RB_ROOT;
     129                 :       2216 :         rb_link_and_balance(&e->subtree_root, &e->subtree_node,
     130                 :            :                         NULL, &e->subtree_root.rb_node);
     131                 :            : err:
     132                 :       2216 :         return e;
     133                 :            : }
     134                 :            : 
     135                 :       1568 : static u32 kid_generate_sub(struct kid_tree *tree, struct kid_entry *e,
     136                 :            :                 struct kid_elem *elem, int *new_id)
     137                 :            : {
     138                 :       1568 :         struct rb_node *node = e->subtree_root.rb_node;
     139                 :       1568 :         struct kid_entry *sub = NULL;
     140                 :            : 
     141                 :       1568 :         struct rb_node **new = &e->subtree_root.rb_node;
     142                 :       1568 :         struct rb_node *parent = NULL;
     143                 :            : 
     144         [ -  + ]:       1568 :         BUG_ON(!node);
     145                 :            : 
     146         [ +  + ]:       3267 :         while (node) {
     147                 :       2384 :                 struct kid_entry *this = rb_entry(node, struct kid_entry, subtree_node);
     148                 :       2384 :                 int ret = sys_kcmp(this->elem.pid, elem->pid, tree->kcmp_type,
     149                 :       4768 :                                 this->elem.idx, elem->idx);
     150                 :            : 
     151                 :       2384 :                 parent = *new;
     152         [ -  + ]:       2384 :                 if (ret < 0)
     153                 :          0 :                         node = node->rb_left, new = &((*new)->rb_left);
     154         [ +  + ]:       2384 :                 else if (ret > 0)
     155                 :       1699 :                         node = node->rb_right, new = &((*new)->rb_right);
     156                 :            :                 else
     157                 :       2384 :                         return this->subid;
     158                 :            :         }
     159                 :            : 
     160                 :        883 :         sub = alloc_kid_entry(tree, elem);
     161         [ +  - ]:        883 :         if (!sub)
     162                 :            :                 return 0;
     163                 :            : 
     164                 :        883 :         rb_link_and_balance(&e->subtree_root, &sub->subtree_node, parent, new);
     165                 :        883 :         *new_id = 1;
     166                 :       1568 :         return sub->subid;
     167                 :            : }
     168                 :            : 
     169                 :       2901 : u32 kid_generate_gen(struct kid_tree *tree,
     170                 :            :                 struct kid_elem *elem, int *new_id)
     171                 :            : {
     172                 :       2901 :         struct rb_node *node = tree->root.rb_node;
     173                 :       2901 :         struct kid_entry *e = NULL;
     174                 :            : 
     175                 :       2901 :         struct rb_node **new = &tree->root.rb_node;
     176                 :       2901 :         struct rb_node *parent = NULL;
     177                 :            : 
     178         [ +  + ]:       4826 :         while (node) {
     179                 :       3493 :                 struct kid_entry *this = rb_entry(node, struct kid_entry, node);
     180                 :            : 
     181                 :       3493 :                 parent = *new;
     182         [ +  + ]:       3493 :                 if (elem->genid < this->elem.genid)
     183                 :        856 :                         node = node->rb_left, new = &((*new)->rb_left);
     184         [ +  + ]:       2637 :                 else if (elem->genid > this->elem.genid)
     185                 :       1069 :                         node = node->rb_right, new = &((*new)->rb_right);
     186                 :            :                 else
     187                 :       3493 :                         return kid_generate_sub(tree, this, elem, new_id);
     188                 :            :         }
     189                 :            : 
     190                 :       1333 :         e = alloc_kid_entry(tree, elem);
     191         [ +  - ]:       1333 :         if (!e)
     192                 :            :                 return 0;
     193                 :            : 
     194                 :       1333 :         rb_link_and_balance(&tree->root, &e->node, parent, new);
     195                 :       1333 :         *new_id = 1;
     196                 :       2901 :         return e->subid;
     197                 :            : 
     198                 :       2216 : }
     199                 :            : 

Generated by: LCOV version 1.9