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_line = 3; 11 static u8 next_dev = 1; 12 static struct rb_root pci_tree = RB_ROOT; 13 14 static struct pci_dev *search(struct rb_root *root, u32 id) 15 { 16 struct rb_node *node = root->rb_node; 17 18 while (node) { 19 struct pci_dev *data = container_of(node, struct pci_dev, node); 20 int result; 21 22 result = id - data->id; 23 24 if (result < 0) 25 node = node->rb_left; 26 else if (result > 0) 27 node = node->rb_right; 28 else 29 return data; 30 } 31 return NULL; 32 } 33 34 static int insert(struct rb_root *root, struct pci_dev *data) 35 { 36 struct rb_node **new = &(root->rb_node), *parent = NULL; 37 38 /* Figure out where to put new node */ 39 while (*new) { 40 struct pci_dev *this = container_of(*new, struct pci_dev, node); 41 int result = data->id - this->id; 42 43 parent = *new; 44 if (result < 0) 45 new = &((*new)->rb_left); 46 else if (result > 0) 47 new = &((*new)->rb_right); 48 else 49 return 0; 50 } 51 52 /* Add new node and rebalance tree. */ 53 rb_link_node(&data->node, parent, new); 54 rb_insert_color(&data->node, root); 55 56 return 1; 57 } 58 59 int irq__register_device(u32 dev, u8 *num, u8 *pin, u8 *line) 60 { 61 struct pci_dev *node; 62 63 node = search(&pci_tree, dev); 64 65 if (!node) { 66 /* We haven't found a node - First device of it's kind */ 67 node = malloc(sizeof(*node)); 68 if (node == NULL) 69 return -1; 70 71 *node = (struct pci_dev) { 72 .id = dev, 73 /* 74 * PCI supports only INTA#,B#,C#,D# per device. 75 * A#,B#,C#,D# are allowed for multifunctional 76 * devices so stick with A# for our single 77 * function devices. 78 */ 79 .pin = 1, 80 }; 81 82 INIT_LIST_HEAD(&node->lines); 83 84 if (insert(&pci_tree, node) != 1) { 85 free(node); 86 return -1; 87 } 88 } 89 90 if (node) { 91 /* This device already has a pin assigned, give out a new line and device id */ 92 struct irq_line *new = malloc(sizeof(*new)); 93 if (new == NULL) 94 return -1; 95 96 new->line = next_line++; 97 *line = new->line; 98 *pin = node->pin; 99 *num = next_dev++; 100 101 list_add(&new->node, &node->lines); 102 103 return 0; 104 } 105 106 return -1; 107 } 108 109 struct rb_node *irq__get_pci_tree(void) 110 { 111 return rb_first(&pci_tree); 112 } 113