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