1 #include "kvm/devices.h"
2 #include "kvm/kvm.h"
3
4 #include <linux/err.h>
5 #include <linux/rbtree.h>
6
7 struct device_bus {
8 struct rb_root root;
9 int dev_num;
10 };
11
12 static struct device_bus device_trees[DEVICE_BUS_MAX] = {
13 [0 ... (DEVICE_BUS_MAX - 1)] = { RB_ROOT, 0 },
14 };
15
device__register(struct device_header * dev)16 int device__register(struct device_header *dev)
17 {
18 struct device_bus *bus;
19 struct rb_node **node, *parent = NULL;
20
21 if (dev->bus_type >= DEVICE_BUS_MAX) {
22 pr_warning("Ignoring device registration on unknown bus %d\n",
23 dev->bus_type);
24 return -EINVAL;
25 }
26
27 bus = &device_trees[dev->bus_type];
28 dev->dev_num = bus->dev_num++;
29
30 node = &bus->root.rb_node;
31 while (*node) {
32 int num = rb_entry(*node, struct device_header, node)->dev_num;
33 int result = dev->dev_num - num;
34
35 parent = *node;
36 if (result < 0)
37 node = &((*node)->rb_left);
38 else if (result > 0)
39 node = &((*node)->rb_right);
40 else
41 return -EEXIST;
42 }
43
44 rb_link_node(&dev->node, parent, node);
45 rb_insert_color(&dev->node, &bus->root);
46 return 0;
47 }
48
device__unregister(struct device_header * dev)49 void device__unregister(struct device_header *dev)
50 {
51 struct device_bus *bus = &device_trees[dev->bus_type];
52 rb_erase(&dev->node, &bus->root);
53 }
54
device__find_dev(enum device_bus_type bus_type,u8 dev_num)55 struct device_header *device__find_dev(enum device_bus_type bus_type, u8 dev_num)
56 {
57 struct rb_node *node;
58
59 if (bus_type >= DEVICE_BUS_MAX)
60 return ERR_PTR(-EINVAL);
61
62 node = device_trees[bus_type].root.rb_node;
63 while (node) {
64 struct device_header *dev = rb_entry(node, struct device_header,
65 node);
66 if (dev_num < dev->dev_num) {
67 node = node->rb_left;
68 } else if (dev_num > dev->dev_num) {
69 node = node->rb_right;
70 } else {
71 return dev;
72 }
73 }
74
75 return NULL;
76 }
77
device__first_dev(enum device_bus_type bus_type)78 struct device_header *device__first_dev(enum device_bus_type bus_type)
79 {
80 struct rb_node *node;
81
82 if (bus_type >= DEVICE_BUS_MAX)
83 return NULL;
84
85 node = rb_first(&device_trees[bus_type].root);
86 return node ? rb_entry(node, struct device_header, node) : NULL;
87 }
88
device__next_dev(struct device_header * dev)89 struct device_header *device__next_dev(struct device_header *dev)
90 {
91 struct rb_node *node = rb_next(&dev->node);
92 return node ? rb_entry(node, struct device_header, node) : NULL;
93 }
94