1 /*
2 * Copyright (c) 2013-2019, Huawei Technologies Co., Ltd. All rights reserved.
3 * Copyright (c) 2020, Huawei Device Co., Ltd. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without modification,
6 * are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice, this list of
9 * conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice, this list
12 * of conditions and the following disclaimer in the documentation and/or other materials
13 * provided with the distribution.
14 *
15 * 3. Neither the name of the copyright holder nor the names of its contributors may be used
16 * to endorse or promote products derived from this software without specific prior written
17 * permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
21 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
26 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
27 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
28 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
29 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 /* Architecture Analysis
33 *********************************************************************************************
34 * The USB Devices Topology --- Translate --> Binary Tree Map
35 * BUS BUS
36 * | /
37 * --------------------- /
38 * | | H01
39 * H01 H02... / \
40 * | | / \
41 * ------------ --------------- H11 \---------H02
42 * | | | | ------\ / \ / \
43 *H11 H12... H21 H22... -------\ / \ / \
44 * | | | | -------/ D1 H12 H21 ...
45 *D1 D2 | D3 ------/ / \ / \
46 * ------------ / \ / \
47 * | | D2 ... H31 \----H22
48 * H31 H32... / \ / \
49 * | | / \ / \
50 * D4 D5 D4 H32 D3 ...
51 * / \
52 * / \
53 * D5 ...
54 *********************************************************************************************
55 */
56
57 #include <stdlib.h>
58 #include <string.h>
59 #include <los_printf_pri.h>
60
61 #include "implementation/usb_btree.h"
62
63
64 #ifdef USB_BINARY_TREE_DEBUG
65 #define BT_DEBUG(x...) dprintf(x)
66 #else
67 #define BT_DEBUG(x...) do{}while(0)
68 #endif
69
70 extern usbd_bt_tree hub_tree;
71
72 struct usbd_bt_node *
usbd_create_bt_node(struct node_info * info)73 usbd_create_bt_node(struct node_info *info)
74 {
75 struct usbd_bt_node *node = (usbd_bt_node *)malloc(sizeof(usbd_bt_node));
76 if (node == NULL) {
77 PRINT_ERR("Binary tree node alloc failed!\n");
78 return (NULL);
79 }
80
81 (void)memset_s(&node->info, sizeof(node->info), 0, sizeof(node->info));
82 node->info.port_no = info->port_no;
83 node->info.nameunit = info->nameunit;
84 node->lbt_node = NULL;
85 node->rbt_node = NULL;
86
87 BT_DEBUG("[create node] %p %s %d\n", node, node->info.nameunit, node->info.port_no);
88 return (node);
89 }
90
91 void
usbd_free_bt_node(usbd_bt_node * node)92 usbd_free_bt_node(usbd_bt_node *node)
93 {
94 BT_DEBUG("[free node] %p %s %d\n", node, node->info.nameunit, node->info.port_no);
95
96 node->info.nameunit = NULL;
97 node->info.port_no = 0;
98 node->lbt_node = NULL;
99 node->rbt_node = NULL;
100
101 free(node);
102 }
103
104 static void
usbd_release_bt_node(usbd_bt_node * node)105 usbd_release_bt_node(usbd_bt_node *node)
106 {
107 if (node == NULL)
108 return;
109
110 usbd_release_bt_node(node->lbt_node);
111 usbd_release_bt_node(node->rbt_node);
112
113 if (node->info.nameunit != NULL)
114 usbd_free_bt_node(node);
115 }
116
117 static struct usbd_bt_node *
usbd_pre_order_bt_node(usbd_bt_node * node,struct node_info * info)118 usbd_pre_order_bt_node(usbd_bt_node *node, struct node_info *info)
119 {
120 usbd_bt_node *l_node, *r_node;
121
122 if (node == NULL) {
123 return (NULL);
124 }
125
126 if (node->info.nameunit == info->nameunit) {
127 if (node->info.port_no == info->port_no) {
128 return (node);
129 }
130 }
131
132 l_node = usbd_pre_order_bt_node(node->lbt_node, info);
133 if (l_node != NULL) {
134 return (l_node);
135 }
136 r_node = usbd_pre_order_bt_node(node->rbt_node, info);
137 if (r_node != NULL) {
138 return (r_node);
139 }
140
141 return (NULL);
142 }
143
144 static bool f_find_device = false;
145 static struct usbd_bt_node *
usbd_pre_order_hub_node(usbd_bt_node * node,char * devname,uint8_t * port_num)146 usbd_pre_order_hub_node(usbd_bt_node *node, char *devname, uint8_t *port_num)
147 {
148 usbd_bt_node *l_node, *r_node;
149
150 if (node == NULL) {
151 return (NULL);
152 }
153
154 if (!strncmp(node->info.nameunit, "uhub", strlen("uhub"))) {
155 BT_DEBUG("[Hub Node] %p %s %d %d\n", node, node->info.nameunit, node->info.port_no, *port_num);
156 if (node->lbt_node == NULL) {
157 (*port_num)--;
158 } else {
159 if (!strncmp(node->lbt_node->info.nameunit, devname, strlen(devname))) {
160 (*port_num)--;
161 if (*port_num == 0)
162 f_find_device = 1;
163 }
164 }
165 if (*port_num == 0) {
166 return (node->lbt_node);
167 }
168 }
169
170 l_node = usbd_pre_order_hub_node(node->lbt_node, devname, port_num);
171 if (l_node != NULL) {
172 return (l_node);
173 }
174 r_node = usbd_pre_order_hub_node(node->rbt_node, devname, port_num);
175 if (r_node != NULL) {
176 return (r_node);
177 }
178 return (NULL);
179 }
180
181 static void
usbd_per_order_hub_quantity(usbd_bt_node * node,uint8_t * port_qty)182 usbd_per_order_hub_quantity(usbd_bt_node *node, uint8_t *port_qty)
183 {
184 if (node == NULL) {
185 return;
186 }
187
188 if (!strncmp(node->info.nameunit, "uhub", strlen("uhub"))) {
189 if (node->lbt_node == NULL) {
190 (*port_qty)++;
191 } else {
192 if (strncmp(node->lbt_node->info.nameunit, "uhub", strlen("uhub"))) {
193 (*port_qty)++;
194 }
195 }
196 }
197
198 usbd_per_order_hub_quantity(node->lbt_node, port_qty);
199 usbd_per_order_hub_quantity(node->rbt_node, port_qty);
200 }
201
202 int
usbd_get_hub_quantity(void)203 usbd_get_hub_quantity(void)
204 {
205 uint8_t quantity = 0;
206
207 usbd_per_order_hub_quantity(hub_tree, &quantity);
208
209 return (quantity);
210 }
211
212 struct usbd_bt_node *
usbd_per_order_probe(usbd_bt_tree tree,char * devname,uint8_t * port_num)213 usbd_per_order_probe(usbd_bt_tree tree, char *devname, uint8_t *port_num)
214 {
215 usbd_bt_node *node = usbd_pre_order_hub_node(tree, devname, port_num);
216
217 if ((node != NULL) && f_find_device) {
218 f_find_device = 0;
219 return (node);
220 }
221
222 return (NULL);
223 }
224
225 int
usbd_insert_bt_node(usbd_bt_node * node,usbd_bt_tree tree,struct node_info * parent_info)226 usbd_insert_bt_node(usbd_bt_node *node, usbd_bt_tree tree, struct node_info *parent_info)
227 {
228 usbd_bt_node *parent_node;
229
230 if ((node == NULL) || (tree == NULL) || (parent_info == NULL))
231 return (-1);
232
233 parent_node = usbd_pre_order_bt_node(tree, parent_info);
234 if (parent_node == NULL) {
235 PRINT_ERR("Find err, insert fail!\n");
236 return (-1);
237 }
238
239 if (parent_node->info.nameunit == node->info.nameunit) { /* The same hub node. */
240 parent_node->rbt_node = node;
241 } else { /* Other driver(hub or other) */
242 parent_node->lbt_node = node;
243 }
244
245 BT_DEBUG("[insert node] parent:%p %s %d\n \
246 %s child :%p %s %d\n", \
247 parent_node, parent_node->info.nameunit, parent_node->info.port_no,
248 (parent_node->info.nameunit == node->info.nameunit ? "right" : "left"),
249 node, node->info.nameunit, node->info.port_no);
250 return (0);
251 }
252
253 int
usbd_remove_bt_node(usbd_bt_tree tree,struct node_info * p_info,struct node_info * rm_info)254 usbd_remove_bt_node(usbd_bt_tree tree, struct node_info *p_info, struct node_info *rm_info)
255 {
256 usbd_bt_node *rm_node;
257
258 if ((tree == NULL) || (p_info == NULL) || (rm_info == NULL))
259 return (-1);
260
261 rm_node = usbd_pre_order_bt_node(tree, rm_info);
262 if (rm_node == NULL) {
263 BT_DEBUG("Find err, remove fail!\n");
264 return (-1);
265 }
266
267 usbd_release_bt_node(rm_node);
268
269 /* release parent left node */
270 rm_node = usbd_pre_order_bt_node(tree, p_info);
271 if (rm_node == NULL) {
272 PRINT_ERR("Parent find err, remove fail!\n");
273 return (-1);
274 }
275 rm_node->lbt_node = NULL;
276
277 return (0);
278 }
279
280