1 #include "kvm/irq.h" 2 3 #include <linux/types.h> 4 #include <linux/rbtree.h> 5 #include <linux/list.h> 6 7 #include <stddef.h> 8 #include <stdlib.h> 9 10 static u8 next_pin = 1; 11 static u8 next_line = 3; 12 static u8 next_dev = 1; 13 static struct rb_root pci_tree = RB_ROOT; 14 15 static struct pci_dev *search(struct rb_root *root, u32 id) 16 { 17 struct rb_node *node = root->rb_node; 18 19 while (node) { 20 struct pci_dev *data = container_of(node, struct pci_dev, node); 21 int result; 22 23 result = id - data->id; 24 25 if (result < 0) 26 node = node->rb_left; 27 else if (result > 0) 28 node = node->rb_right; 29 else 30 return data; 31 } 32 return NULL; 33 } 34 35 static int insert(struct rb_root *root, struct pci_dev *data) 36 { 37 struct rb_node **new = &(root->rb_node), *parent = NULL; 38 39 /* Figure out where to put new node */ 40 while (*new) { 41 struct pci_dev *this = container_of(*new, struct pci_dev, node); 42 int result = data->id - this->id; 43 44 parent = *new; 45 if (result < 0) 46 new = &((*new)->rb_left); 47 else if (result > 0) 48 new = &((*new)->rb_right); 49 else 50 return 0; 51 } 52 53 /* Add new node and rebalance tree. */ 54 rb_link_node(&data->node, parent, new); 55 rb_insert_color(&data->node, root); 56 57 return 1; 58 } 59 60 int irq__register_device(u32 dev, u8 *num, u8 *pin, u8 *line) 61 { 62 struct pci_dev *node; 63 64 node = search(&pci_tree, dev); 65 66 if (!node) { 67 /* We haven't found a node - First device of it's kind */ 68 node = malloc(sizeof(*node)); 69 if (node == NULL) 70 return -1; 71 72 *node = (struct pci_dev) { 73 .id = dev, 74 .pin = next_pin++, 75 }; 76 77 INIT_LIST_HEAD(&node->lines); 78 79 if (insert(&pci_tree, node) != 1) { 80 free(node); 81 return -1; 82 } 83 } 84 85 if (node) { 86 /* This device already has a pin assigned, give out a new line and device id */ 87 struct irq_line *new = malloc(sizeof(*new)); 88 if (new == NULL) 89 return -1; 90 91 new->line = next_line++; 92 *line = new->line; 93 *pin = node->pin; 94 *num = next_dev++; 95 96 list_add(&new->node, &node->lines); 97 98 return 0; 99 } 100 101 return -1; 102 } 103 104 struct rb_node *irq__get_pci_tree(void) 105 { 106 return rb_first(&pci_tree); 107 } 108