Commit | Line | Data |
---|---|---|
c781c06d KH |
1 | /* |
2 | * Incremental bus scan, based on bus topology | |
3038e353 KH |
3 | * |
4 | * Copyright (C) 2004-2006 Kristian Hoegsberg <krh@bitplanet.net> | |
5 | * | |
6 | * This program is free software; you can redistribute it and/or modify | |
7 | * it under the terms of the GNU General Public License as published by | |
8 | * the Free Software Foundation; either version 2 of the License, or | |
9 | * (at your option) any later version. | |
10 | * | |
11 | * This program is distributed in the hope that it will be useful, | |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | * GNU General Public License for more details. | |
15 | * | |
16 | * You should have received a copy of the GNU General Public License | |
17 | * along with this program; if not, write to the Free Software Foundation, | |
18 | * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. | |
19 | */ | |
20 | ||
21 | #include <linux/module.h> | |
22 | #include <linux/wait.h> | |
23 | #include <linux/errno.h> | |
24 | #include "fw-transaction.h" | |
25 | #include "fw-topology.h" | |
26 | ||
a77754a7 KH |
27 | #define SELF_ID_PHY_ID(q) (((q) >> 24) & 0x3f) |
28 | #define SELF_ID_EXTENDED(q) (((q) >> 23) & 0x01) | |
29 | #define SELF_ID_LINK_ON(q) (((q) >> 22) & 0x01) | |
30 | #define SELF_ID_GAP_COUNT(q) (((q) >> 16) & 0x3f) | |
31 | #define SELF_ID_PHY_SPEED(q) (((q) >> 14) & 0x03) | |
32 | #define SELF_ID_CONTENDER(q) (((q) >> 11) & 0x01) | |
33 | #define SELF_ID_PHY_INITIATOR(q) (((q) >> 1) & 0x01) | |
34 | #define SELF_ID_MORE_PACKETS(q) (((q) >> 0) & 0x01) | |
3038e353 | 35 | |
a77754a7 | 36 | #define SELF_ID_EXT_SEQUENCE(q) (((q) >> 20) & 0x07) |
3038e353 KH |
37 | |
38 | static u32 *count_ports(u32 *sid, int *total_port_count, int *child_port_count) | |
39 | { | |
40 | u32 q; | |
41 | int port_type, shift, seq; | |
42 | ||
43 | *total_port_count = 0; | |
44 | *child_port_count = 0; | |
45 | ||
46 | shift = 6; | |
47 | q = *sid; | |
48 | seq = 0; | |
49 | ||
50 | while (1) { | |
51 | port_type = (q >> shift) & 0x03; | |
52 | switch (port_type) { | |
53 | case SELFID_PORT_CHILD: | |
54 | (*child_port_count)++; | |
55 | case SELFID_PORT_PARENT: | |
56 | case SELFID_PORT_NCONN: | |
57 | (*total_port_count)++; | |
58 | case SELFID_PORT_NONE: | |
59 | break; | |
60 | } | |
61 | ||
62 | shift -= 2; | |
63 | if (shift == 0) { | |
a77754a7 | 64 | if (!SELF_ID_MORE_PACKETS(q)) |
3038e353 KH |
65 | return sid + 1; |
66 | ||
67 | shift = 16; | |
68 | sid++; | |
69 | q = *sid; | |
70 | ||
c781c06d KH |
71 | /* |
72 | * Check that the extra packets actually are | |
3038e353 KH |
73 | * extended self ID packets and that the |
74 | * sequence numbers in the extended self ID | |
c781c06d KH |
75 | * packets increase as expected. |
76 | */ | |
3038e353 | 77 | |
a77754a7 KH |
78 | if (!SELF_ID_EXTENDED(q) || |
79 | seq != SELF_ID_EXT_SEQUENCE(q)) | |
3038e353 KH |
80 | return NULL; |
81 | ||
82 | seq++; | |
83 | } | |
84 | } | |
85 | } | |
86 | ||
87 | static int get_port_type(u32 *sid, int port_index) | |
88 | { | |
89 | int index, shift; | |
90 | ||
91 | index = (port_index + 5) / 8; | |
92 | shift = 16 - ((port_index + 5) & 7) * 2; | |
93 | return (sid[index] >> shift) & 0x03; | |
94 | } | |
95 | ||
95688e97 | 96 | static struct fw_node *fw_node_create(u32 sid, int port_count, int color) |
3038e353 KH |
97 | { |
98 | struct fw_node *node; | |
99 | ||
2d826cc5 | 100 | node = kzalloc(sizeof(*node) + port_count * sizeof(node->ports[0]), |
3038e353 KH |
101 | GFP_ATOMIC); |
102 | if (node == NULL) | |
103 | return NULL; | |
104 | ||
105 | node->color = color; | |
a77754a7 KH |
106 | node->node_id = LOCAL_BUS | SELF_ID_PHY_ID(sid); |
107 | node->link_on = SELF_ID_LINK_ON(sid); | |
108 | node->phy_speed = SELF_ID_PHY_SPEED(sid); | |
3038e353 KH |
109 | node->port_count = port_count; |
110 | ||
111 | atomic_set(&node->ref_count, 1); | |
112 | INIT_LIST_HEAD(&node->link); | |
113 | ||
114 | return node; | |
115 | } | |
116 | ||
c781c06d KH |
117 | /* |
118 | * Compute the maximum hop count for this node and it's children. The | |
83db801c KH |
119 | * maximum hop count is the maximum number of connections between any |
120 | * two nodes in the subtree rooted at this node. We need this for | |
121 | * setting the gap count. As we build the tree bottom up in | |
122 | * build_tree() below, this is fairly easy to do: for each node we | |
123 | * maintain the max hop count and the max depth, ie the number of hops | |
124 | * to the furthest leaf. Computing the max hop count breaks down into | |
125 | * two cases: either the path goes through this node, in which case | |
126 | * the hop count is the sum of the two biggest child depths plus 2. | |
127 | * Or it could be the case that the max hop path is entirely | |
128 | * containted in a child tree, in which case the max hop count is just | |
129 | * the max hop count of this child. | |
130 | */ | |
131 | static void update_hop_count(struct fw_node *node) | |
132 | { | |
133 | int depths[2] = { -1, -1 }; | |
134 | int max_child_hops = 0; | |
135 | int i; | |
136 | ||
137 | for (i = 0; i < node->port_count; i++) { | |
dae1a3aa | 138 | if (node->ports[i] == NULL) |
83db801c KH |
139 | continue; |
140 | ||
dae1a3aa SR |
141 | if (node->ports[i]->max_hops > max_child_hops) |
142 | max_child_hops = node->ports[i]->max_hops; | |
83db801c | 143 | |
dae1a3aa | 144 | if (node->ports[i]->max_depth > depths[0]) { |
83db801c | 145 | depths[1] = depths[0]; |
dae1a3aa SR |
146 | depths[0] = node->ports[i]->max_depth; |
147 | } else if (node->ports[i]->max_depth > depths[1]) | |
148 | depths[1] = node->ports[i]->max_depth; | |
83db801c KH |
149 | } |
150 | ||
151 | node->max_depth = depths[0] + 1; | |
152 | node->max_hops = max(max_child_hops, depths[0] + depths[1] + 2); | |
153 | } | |
154 | ||
e5f84f82 SR |
155 | static inline struct fw_node *fw_node(struct list_head *l) |
156 | { | |
157 | return list_entry(l, struct fw_node, link); | |
158 | } | |
83db801c | 159 | |
3038e353 KH |
160 | /** |
161 | * build_tree - Build the tree representation of the topology | |
162 | * @self_ids: array of self IDs to create the tree from | |
163 | * @self_id_count: the length of the self_ids array | |
164 | * @local_id: the node ID of the local node | |
165 | * | |
166 | * This function builds the tree representation of the topology given | |
167 | * by the self IDs from the latest bus reset. During the construction | |
168 | * of the tree, the function checks that the self IDs are valid and | |
c1b91ce4 | 169 | * internally consistent. On succcess this function returns the |
3038e353 KH |
170 | * fw_node corresponding to the local card otherwise NULL. |
171 | */ | |
473d28c7 KH |
172 | static struct fw_node *build_tree(struct fw_card *card, |
173 | u32 *sid, int self_id_count) | |
3038e353 | 174 | { |
93e4fd45 | 175 | struct fw_node *node, *child, *local_node, *irm_node; |
3038e353 | 176 | struct list_head stack, *h; |
473d28c7 | 177 | u32 *next_sid, *end, q; |
3038e353 | 178 | int i, port_count, child_port_count, phy_id, parent_count, stack_depth; |
24d40125 SR |
179 | int gap_count; |
180 | bool beta_repeaters_present; | |
3038e353 KH |
181 | |
182 | local_node = NULL; | |
183 | node = NULL; | |
184 | INIT_LIST_HEAD(&stack); | |
185 | stack_depth = 0; | |
473d28c7 | 186 | end = sid + self_id_count; |
3038e353 | 187 | phy_id = 0; |
93e4fd45 | 188 | irm_node = NULL; |
a77754a7 | 189 | gap_count = SELF_ID_GAP_COUNT(*sid); |
24d40125 | 190 | beta_repeaters_present = false; |
3038e353 KH |
191 | |
192 | while (sid < end) { | |
193 | next_sid = count_ports(sid, &port_count, &child_port_count); | |
194 | ||
195 | if (next_sid == NULL) { | |
196 | fw_error("Inconsistent extended self IDs.\n"); | |
197 | return NULL; | |
198 | } | |
199 | ||
200 | q = *sid; | |
a77754a7 | 201 | if (phy_id != SELF_ID_PHY_ID(q)) { |
3038e353 | 202 | fw_error("PHY ID mismatch in self ID: %d != %d.\n", |
a77754a7 | 203 | phy_id, SELF_ID_PHY_ID(q)); |
3038e353 KH |
204 | return NULL; |
205 | } | |
206 | ||
207 | if (child_port_count > stack_depth) { | |
208 | fw_error("Topology stack underflow\n"); | |
209 | return NULL; | |
210 | } | |
211 | ||
c781c06d KH |
212 | /* |
213 | * Seek back from the top of our stack to find the | |
214 | * start of the child nodes for this node. | |
215 | */ | |
3038e353 KH |
216 | for (i = 0, h = &stack; i < child_port_count; i++) |
217 | h = h->prev; | |
c1b91ce4 YD |
218 | /* |
219 | * When the stack is empty, this yields an invalid value, | |
220 | * but that pointer will never be dereferenced. | |
221 | */ | |
3038e353 KH |
222 | child = fw_node(h); |
223 | ||
224 | node = fw_node_create(q, port_count, card->color); | |
225 | if (node == NULL) { | |
8a8cea27 | 226 | fw_error("Out of memory while building topology.\n"); |
3038e353 KH |
227 | return NULL; |
228 | } | |
229 | ||
230 | if (phy_id == (card->node_id & 0x3f)) | |
231 | local_node = node; | |
232 | ||
a77754a7 | 233 | if (SELF_ID_CONTENDER(q)) |
93e4fd45 | 234 | irm_node = node; |
3038e353 KH |
235 | |
236 | parent_count = 0; | |
237 | ||
238 | for (i = 0; i < port_count; i++) { | |
239 | switch (get_port_type(sid, i)) { | |
240 | case SELFID_PORT_PARENT: | |
c781c06d KH |
241 | /* |
242 | * Who's your daddy? We dont know the | |
3038e353 KH |
243 | * parent node at this time, so we |
244 | * temporarily abuse node->color for | |
245 | * remembering the entry in the | |
246 | * node->ports array where the parent | |
247 | * node should be. Later, when we | |
248 | * handle the parent node, we fix up | |
249 | * the reference. | |
250 | */ | |
251 | parent_count++; | |
252 | node->color = i; | |
253 | break; | |
254 | ||
255 | case SELFID_PORT_CHILD: | |
dae1a3aa | 256 | node->ports[i] = child; |
c781c06d KH |
257 | /* |
258 | * Fix up parent reference for this | |
259 | * child node. | |
260 | */ | |
dae1a3aa | 261 | child->ports[child->color] = node; |
3038e353 KH |
262 | child->color = card->color; |
263 | child = fw_node(child->link.next); | |
264 | break; | |
265 | } | |
266 | } | |
267 | ||
c781c06d KH |
268 | /* |
269 | * Check that the node reports exactly one parent | |
3038e353 | 270 | * port, except for the root, which of course should |
c781c06d KH |
271 | * have no parents. |
272 | */ | |
3038e353 KH |
273 | if ((next_sid == end && parent_count != 0) || |
274 | (next_sid < end && parent_count != 1)) { | |
275 | fw_error("Parent port inconsistency for node %d: " | |
276 | "parent_count=%d\n", phy_id, parent_count); | |
277 | return NULL; | |
278 | } | |
279 | ||
280 | /* Pop the child nodes off the stack and push the new node. */ | |
281 | __list_del(h->prev, &stack); | |
282 | list_add_tail(&node->link, &stack); | |
283 | stack_depth += 1 - child_port_count; | |
284 | ||
24d40125 SR |
285 | if (node->phy_speed == SCODE_BETA && |
286 | parent_count + child_port_count > 1) | |
287 | beta_repeaters_present = true; | |
288 | ||
c781c06d KH |
289 | /* |
290 | * If all PHYs does not report the same gap count | |
83db801c | 291 | * setting, we fall back to 63 which will force a gap |
c781c06d KH |
292 | * count reconfiguration and a reset. |
293 | */ | |
a77754a7 | 294 | if (SELF_ID_GAP_COUNT(q) != gap_count) |
83db801c KH |
295 | gap_count = 63; |
296 | ||
297 | update_hop_count(node); | |
298 | ||
3038e353 KH |
299 | sid = next_sid; |
300 | phy_id++; | |
301 | } | |
302 | ||
303 | card->root_node = node; | |
93e4fd45 | 304 | card->irm_node = irm_node; |
83db801c | 305 | card->gap_count = gap_count; |
24d40125 | 306 | card->beta_repeaters_present = beta_repeaters_present; |
3038e353 KH |
307 | |
308 | return local_node; | |
309 | } | |
310 | ||
a98e2719 KH |
311 | typedef void (*fw_node_callback_t)(struct fw_card * card, |
312 | struct fw_node * node, | |
313 | struct fw_node * parent); | |
3038e353 KH |
314 | |
315 | static void | |
316 | for_each_fw_node(struct fw_card *card, struct fw_node *root, | |
317 | fw_node_callback_t callback) | |
318 | { | |
319 | struct list_head list; | |
320 | struct fw_node *node, *next, *child, *parent; | |
321 | int i; | |
322 | ||
323 | INIT_LIST_HEAD(&list); | |
324 | ||
325 | fw_node_get(root); | |
326 | list_add_tail(&root->link, &list); | |
327 | parent = NULL; | |
328 | list_for_each_entry(node, &list, link) { | |
329 | node->color = card->color; | |
330 | ||
331 | for (i = 0; i < node->port_count; i++) { | |
dae1a3aa | 332 | child = node->ports[i]; |
3038e353 KH |
333 | if (!child) |
334 | continue; | |
335 | if (child->color == card->color) | |
336 | parent = child; | |
337 | else { | |
338 | fw_node_get(child); | |
339 | list_add_tail(&child->link, &list); | |
340 | } | |
341 | } | |
342 | ||
343 | callback(card, node, parent); | |
344 | } | |
345 | ||
346 | list_for_each_entry_safe(node, next, &list, link) | |
347 | fw_node_put(node); | |
348 | } | |
349 | ||
350 | static void | |
351 | report_lost_node(struct fw_card *card, | |
352 | struct fw_node *node, struct fw_node *parent) | |
353 | { | |
354 | fw_node_event(card, node, FW_NODE_DESTROYED); | |
355 | fw_node_put(node); | |
356 | } | |
357 | ||
358 | static void | |
359 | report_found_node(struct fw_card *card, | |
360 | struct fw_node *node, struct fw_node *parent) | |
361 | { | |
362 | int b_path = (node->phy_speed == SCODE_BETA); | |
363 | ||
364 | if (parent != NULL) { | |
748086eb SR |
365 | /* min() macro doesn't work here with gcc 3.4 */ |
366 | node->max_speed = parent->max_speed < node->phy_speed ? | |
367 | parent->max_speed : node->phy_speed; | |
3038e353 KH |
368 | node->b_path = parent->b_path && b_path; |
369 | } else { | |
370 | node->max_speed = node->phy_speed; | |
371 | node->b_path = b_path; | |
372 | } | |
373 | ||
374 | fw_node_event(card, node, FW_NODE_CREATED); | |
375 | } | |
376 | ||
377 | void fw_destroy_nodes(struct fw_card *card) | |
378 | { | |
379 | unsigned long flags; | |
380 | ||
381 | spin_lock_irqsave(&card->lock, flags); | |
382 | card->color++; | |
383 | if (card->local_node != NULL) | |
384 | for_each_fw_node(card, card->local_node, report_lost_node); | |
385 | spin_unlock_irqrestore(&card->lock, flags); | |
386 | } | |
387 | ||
388 | static void move_tree(struct fw_node *node0, struct fw_node *node1, int port) | |
389 | { | |
390 | struct fw_node *tree; | |
391 | int i; | |
392 | ||
dae1a3aa SR |
393 | tree = node1->ports[port]; |
394 | node0->ports[port] = tree; | |
3038e353 | 395 | for (i = 0; i < tree->port_count; i++) { |
dae1a3aa SR |
396 | if (tree->ports[i] == node1) { |
397 | tree->ports[i] = node0; | |
3038e353 KH |
398 | break; |
399 | } | |
400 | } | |
401 | } | |
402 | ||
403 | /** | |
404 | * update_tree - compare the old topology tree for card with the new | |
405 | * one specified by root. Queue the nodes and mark them as either | |
406 | * found, lost or updated. Update the nodes in the card topology tree | |
407 | * as we go. | |
408 | */ | |
409 | static void | |
83db801c | 410 | update_tree(struct fw_card *card, struct fw_node *root) |
3038e353 KH |
411 | { |
412 | struct list_head list0, list1; | |
413 | struct fw_node *node0, *node1; | |
414 | int i, event; | |
415 | ||
416 | INIT_LIST_HEAD(&list0); | |
417 | list_add_tail(&card->local_node->link, &list0); | |
418 | INIT_LIST_HEAD(&list1); | |
419 | list_add_tail(&root->link, &list1); | |
420 | ||
421 | node0 = fw_node(list0.next); | |
422 | node1 = fw_node(list1.next); | |
3038e353 KH |
423 | |
424 | while (&node0->link != &list0) { | |
425 | ||
426 | /* assert(node0->port_count == node1->port_count); */ | |
427 | if (node0->link_on && !node1->link_on) | |
428 | event = FW_NODE_LINK_OFF; | |
429 | else if (!node0->link_on && node1->link_on) | |
430 | event = FW_NODE_LINK_ON; | |
431 | else | |
432 | event = FW_NODE_UPDATED; | |
433 | ||
434 | node0->node_id = node1->node_id; | |
435 | node0->color = card->color; | |
436 | node0->link_on = node1->link_on; | |
437 | node0->initiated_reset = node1->initiated_reset; | |
83db801c | 438 | node0->max_hops = node1->max_hops; |
3038e353 KH |
439 | node1->color = card->color; |
440 | fw_node_event(card, node0, event); | |
441 | ||
442 | if (card->root_node == node1) | |
443 | card->root_node = node0; | |
444 | if (card->irm_node == node1) | |
445 | card->irm_node = node0; | |
446 | ||
447 | for (i = 0; i < node0->port_count; i++) { | |
dae1a3aa | 448 | if (node0->ports[i] && node1->ports[i]) { |
c781c06d KH |
449 | /* |
450 | * This port didn't change, queue the | |
3038e353 | 451 | * connected node for further |
c781c06d KH |
452 | * investigation. |
453 | */ | |
dae1a3aa | 454 | if (node0->ports[i]->color == card->color) |
3038e353 | 455 | continue; |
dae1a3aa SR |
456 | list_add_tail(&node0->ports[i]->link, &list0); |
457 | list_add_tail(&node1->ports[i]->link, &list1); | |
458 | } else if (node0->ports[i]) { | |
c781c06d KH |
459 | /* |
460 | * The nodes connected here were | |
3038e353 KH |
461 | * unplugged; unref the lost nodes and |
462 | * queue FW_NODE_LOST callbacks for | |
c781c06d KH |
463 | * them. |
464 | */ | |
3038e353 | 465 | |
dae1a3aa | 466 | for_each_fw_node(card, node0->ports[i], |
3038e353 | 467 | report_lost_node); |
dae1a3aa SR |
468 | node0->ports[i] = NULL; |
469 | } else if (node1->ports[i]) { | |
c781c06d KH |
470 | /* |
471 | * One or more node were connected to | |
3038e353 KH |
472 | * this port. Move the new nodes into |
473 | * the tree and queue FW_NODE_CREATED | |
c781c06d KH |
474 | * callbacks for them. |
475 | */ | |
3038e353 | 476 | move_tree(node0, node1, i); |
dae1a3aa | 477 | for_each_fw_node(card, node0->ports[i], |
3038e353 | 478 | report_found_node); |
3038e353 KH |
479 | } |
480 | } | |
481 | ||
482 | node0 = fw_node(node0->link.next); | |
483 | node1 = fw_node(node1->link.next); | |
484 | } | |
485 | } | |
486 | ||
473d28c7 KH |
487 | static void |
488 | update_topology_map(struct fw_card *card, u32 *self_ids, int self_id_count) | |
489 | { | |
490 | int node_count; | |
473d28c7 KH |
491 | |
492 | card->topology_map[1]++; | |
493 | node_count = (card->root_node->node_id & 0x3f) + 1; | |
494 | card->topology_map[2] = (node_count << 16) | self_id_count; | |
e175569c | 495 | card->topology_map[0] = (self_id_count + 2) << 16; |
473d28c7 | 496 | memcpy(&card->topology_map[3], self_ids, self_id_count * 4); |
e175569c | 497 | fw_compute_block_crc(card->topology_map); |
473d28c7 KH |
498 | } |
499 | ||
3038e353 KH |
500 | void |
501 | fw_core_handle_bus_reset(struct fw_card *card, | |
502 | int node_id, int generation, | |
503 | int self_id_count, u32 * self_ids) | |
504 | { | |
505 | struct fw_node *local_node; | |
506 | unsigned long flags; | |
3038e353 KH |
507 | |
508 | fw_flush_transactions(card); | |
509 | ||
510 | spin_lock_irqsave(&card->lock, flags); | |
511 | ||
c781c06d KH |
512 | /* |
513 | * If the new topology has a different self_id_count the topology | |
83db801c | 514 | * changed, either nodes were added or removed. In that case we |
c781c06d KH |
515 | * reset the IRM reset counter. |
516 | */ | |
83db801c | 517 | if (card->self_id_count != self_id_count) |
931c4834 | 518 | card->bm_retries = 0; |
83db801c | 519 | |
3038e353 | 520 | card->node_id = node_id; |
3038e353 | 521 | card->generation = generation; |
931c4834 | 522 | card->reset_jiffies = jiffies; |
993baca3 | 523 | schedule_delayed_work(&card->work, 0); |
3038e353 | 524 | |
473d28c7 KH |
525 | local_node = build_tree(card, self_ids, self_id_count); |
526 | ||
527 | update_topology_map(card, self_ids, self_id_count); | |
3038e353 KH |
528 | |
529 | card->color++; | |
530 | ||
531 | if (local_node == NULL) { | |
532 | fw_error("topology build failed\n"); | |
533 | /* FIXME: We need to issue a bus reset in this case. */ | |
534 | } else if (card->local_node == NULL) { | |
535 | card->local_node = local_node; | |
536 | for_each_fw_node(card, local_node, report_found_node); | |
537 | } else { | |
83db801c | 538 | update_tree(card, local_node); |
3038e353 KH |
539 | } |
540 | ||
541 | spin_unlock_irqrestore(&card->lock, flags); | |
542 | } | |
3038e353 | 543 | EXPORT_SYMBOL(fw_core_handle_bus_reset); |