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++) { | |
138 | if (node->ports[i].node == NULL) | |
139 | continue; | |
140 | ||
141 | if (node->ports[i].node->max_hops > max_child_hops) | |
142 | max_child_hops = node->ports[i].node->max_hops; | |
143 | ||
144 | if (node->ports[i].node->max_depth > depths[0]) { | |
145 | depths[1] = depths[0]; | |
146 | depths[0] = node->ports[i].node->max_depth; | |
147 | } else if (node->ports[i].node->max_depth > depths[1]) | |
148 | depths[1] = node->ports[i].node->max_depth; | |
149 | } | |
150 | ||
151 | node->max_depth = depths[0] + 1; | |
152 | node->max_hops = max(max_child_hops, depths[0] + depths[1] + 2); | |
153 | } | |
154 | ||
155 | ||
3038e353 KH |
156 | /** |
157 | * build_tree - Build the tree representation of the topology | |
158 | * @self_ids: array of self IDs to create the tree from | |
159 | * @self_id_count: the length of the self_ids array | |
160 | * @local_id: the node ID of the local node | |
161 | * | |
162 | * This function builds the tree representation of the topology given | |
163 | * by the self IDs from the latest bus reset. During the construction | |
164 | * of the tree, the function checks that the self IDs are valid and | |
165 | * internally consistent. On succcess this funtions returns the | |
166 | * fw_node corresponding to the local card otherwise NULL. | |
167 | */ | |
473d28c7 KH |
168 | static struct fw_node *build_tree(struct fw_card *card, |
169 | u32 *sid, int self_id_count) | |
3038e353 | 170 | { |
93e4fd45 | 171 | struct fw_node *node, *child, *local_node, *irm_node; |
3038e353 | 172 | struct list_head stack, *h; |
473d28c7 | 173 | u32 *next_sid, *end, q; |
3038e353 | 174 | int i, port_count, child_port_count, phy_id, parent_count, stack_depth; |
83db801c | 175 | int gap_count, topology_type; |
3038e353 KH |
176 | |
177 | local_node = NULL; | |
178 | node = NULL; | |
179 | INIT_LIST_HEAD(&stack); | |
180 | stack_depth = 0; | |
473d28c7 | 181 | end = sid + self_id_count; |
3038e353 | 182 | phy_id = 0; |
93e4fd45 | 183 | irm_node = NULL; |
a77754a7 | 184 | gap_count = SELF_ID_GAP_COUNT(*sid); |
83db801c | 185 | topology_type = 0; |
3038e353 KH |
186 | |
187 | while (sid < end) { | |
188 | next_sid = count_ports(sid, &port_count, &child_port_count); | |
189 | ||
190 | if (next_sid == NULL) { | |
191 | fw_error("Inconsistent extended self IDs.\n"); | |
192 | return NULL; | |
193 | } | |
194 | ||
195 | q = *sid; | |
a77754a7 | 196 | if (phy_id != SELF_ID_PHY_ID(q)) { |
3038e353 | 197 | fw_error("PHY ID mismatch in self ID: %d != %d.\n", |
a77754a7 | 198 | phy_id, SELF_ID_PHY_ID(q)); |
3038e353 KH |
199 | return NULL; |
200 | } | |
201 | ||
202 | if (child_port_count > stack_depth) { | |
203 | fw_error("Topology stack underflow\n"); | |
204 | return NULL; | |
205 | } | |
206 | ||
c781c06d KH |
207 | /* |
208 | * Seek back from the top of our stack to find the | |
209 | * start of the child nodes for this node. | |
210 | */ | |
3038e353 KH |
211 | for (i = 0, h = &stack; i < child_port_count; i++) |
212 | h = h->prev; | |
213 | child = fw_node(h); | |
214 | ||
215 | node = fw_node_create(q, port_count, card->color); | |
216 | if (node == NULL) { | |
217 | fw_error("Out of memory while building topology."); | |
218 | return NULL; | |
219 | } | |
220 | ||
221 | if (phy_id == (card->node_id & 0x3f)) | |
222 | local_node = node; | |
223 | ||
a77754a7 | 224 | if (SELF_ID_CONTENDER(q)) |
93e4fd45 | 225 | irm_node = node; |
3038e353 | 226 | |
83db801c KH |
227 | if (node->phy_speed == SCODE_BETA) |
228 | topology_type |= FW_TOPOLOGY_B; | |
229 | else | |
230 | topology_type |= FW_TOPOLOGY_A; | |
231 | ||
3038e353 KH |
232 | parent_count = 0; |
233 | ||
234 | for (i = 0; i < port_count; i++) { | |
235 | switch (get_port_type(sid, i)) { | |
236 | case SELFID_PORT_PARENT: | |
c781c06d KH |
237 | /* |
238 | * Who's your daddy? We dont know the | |
3038e353 KH |
239 | * parent node at this time, so we |
240 | * temporarily abuse node->color for | |
241 | * remembering the entry in the | |
242 | * node->ports array where the parent | |
243 | * node should be. Later, when we | |
244 | * handle the parent node, we fix up | |
245 | * the reference. | |
246 | */ | |
247 | parent_count++; | |
248 | node->color = i; | |
249 | break; | |
250 | ||
251 | case SELFID_PORT_CHILD: | |
252 | node->ports[i].node = child; | |
c781c06d KH |
253 | /* |
254 | * Fix up parent reference for this | |
255 | * child node. | |
256 | */ | |
3038e353 KH |
257 | child->ports[child->color].node = node; |
258 | child->color = card->color; | |
259 | child = fw_node(child->link.next); | |
260 | break; | |
261 | } | |
262 | } | |
263 | ||
c781c06d KH |
264 | /* |
265 | * Check that the node reports exactly one parent | |
3038e353 | 266 | * port, except for the root, which of course should |
c781c06d KH |
267 | * have no parents. |
268 | */ | |
3038e353 KH |
269 | if ((next_sid == end && parent_count != 0) || |
270 | (next_sid < end && parent_count != 1)) { | |
271 | fw_error("Parent port inconsistency for node %d: " | |
272 | "parent_count=%d\n", phy_id, parent_count); | |
273 | return NULL; | |
274 | } | |
275 | ||
276 | /* Pop the child nodes off the stack and push the new node. */ | |
277 | __list_del(h->prev, &stack); | |
278 | list_add_tail(&node->link, &stack); | |
279 | stack_depth += 1 - child_port_count; | |
280 | ||
c781c06d KH |
281 | /* |
282 | * If all PHYs does not report the same gap count | |
83db801c | 283 | * setting, we fall back to 63 which will force a gap |
c781c06d KH |
284 | * count reconfiguration and a reset. |
285 | */ | |
a77754a7 | 286 | if (SELF_ID_GAP_COUNT(q) != gap_count) |
83db801c KH |
287 | gap_count = 63; |
288 | ||
289 | update_hop_count(node); | |
290 | ||
3038e353 KH |
291 | sid = next_sid; |
292 | phy_id++; | |
293 | } | |
294 | ||
295 | card->root_node = node; | |
93e4fd45 | 296 | card->irm_node = irm_node; |
83db801c KH |
297 | card->gap_count = gap_count; |
298 | card->topology_type = topology_type; | |
3038e353 KH |
299 | |
300 | return local_node; | |
301 | } | |
302 | ||
a98e2719 KH |
303 | typedef void (*fw_node_callback_t)(struct fw_card * card, |
304 | struct fw_node * node, | |
305 | struct fw_node * parent); | |
3038e353 KH |
306 | |
307 | static void | |
308 | for_each_fw_node(struct fw_card *card, struct fw_node *root, | |
309 | fw_node_callback_t callback) | |
310 | { | |
311 | struct list_head list; | |
312 | struct fw_node *node, *next, *child, *parent; | |
313 | int i; | |
314 | ||
315 | INIT_LIST_HEAD(&list); | |
316 | ||
317 | fw_node_get(root); | |
318 | list_add_tail(&root->link, &list); | |
319 | parent = NULL; | |
320 | list_for_each_entry(node, &list, link) { | |
321 | node->color = card->color; | |
322 | ||
323 | for (i = 0; i < node->port_count; i++) { | |
324 | child = node->ports[i].node; | |
325 | if (!child) | |
326 | continue; | |
327 | if (child->color == card->color) | |
328 | parent = child; | |
329 | else { | |
330 | fw_node_get(child); | |
331 | list_add_tail(&child->link, &list); | |
332 | } | |
333 | } | |
334 | ||
335 | callback(card, node, parent); | |
336 | } | |
337 | ||
338 | list_for_each_entry_safe(node, next, &list, link) | |
339 | fw_node_put(node); | |
340 | } | |
341 | ||
342 | static void | |
343 | report_lost_node(struct fw_card *card, | |
344 | struct fw_node *node, struct fw_node *parent) | |
345 | { | |
346 | fw_node_event(card, node, FW_NODE_DESTROYED); | |
347 | fw_node_put(node); | |
348 | } | |
349 | ||
350 | static void | |
351 | report_found_node(struct fw_card *card, | |
352 | struct fw_node *node, struct fw_node *parent) | |
353 | { | |
354 | int b_path = (node->phy_speed == SCODE_BETA); | |
355 | ||
356 | if (parent != NULL) { | |
748086eb SR |
357 | /* min() macro doesn't work here with gcc 3.4 */ |
358 | node->max_speed = parent->max_speed < node->phy_speed ? | |
359 | parent->max_speed : node->phy_speed; | |
3038e353 KH |
360 | node->b_path = parent->b_path && b_path; |
361 | } else { | |
362 | node->max_speed = node->phy_speed; | |
363 | node->b_path = b_path; | |
364 | } | |
365 | ||
366 | fw_node_event(card, node, FW_NODE_CREATED); | |
367 | } | |
368 | ||
369 | void fw_destroy_nodes(struct fw_card *card) | |
370 | { | |
371 | unsigned long flags; | |
372 | ||
373 | spin_lock_irqsave(&card->lock, flags); | |
374 | card->color++; | |
375 | if (card->local_node != NULL) | |
376 | for_each_fw_node(card, card->local_node, report_lost_node); | |
377 | spin_unlock_irqrestore(&card->lock, flags); | |
378 | } | |
379 | ||
380 | static void move_tree(struct fw_node *node0, struct fw_node *node1, int port) | |
381 | { | |
382 | struct fw_node *tree; | |
383 | int i; | |
384 | ||
385 | tree = node1->ports[port].node; | |
386 | node0->ports[port].node = tree; | |
387 | for (i = 0; i < tree->port_count; i++) { | |
388 | if (tree->ports[i].node == node1) { | |
389 | tree->ports[i].node = node0; | |
390 | break; | |
391 | } | |
392 | } | |
393 | } | |
394 | ||
395 | /** | |
396 | * update_tree - compare the old topology tree for card with the new | |
397 | * one specified by root. Queue the nodes and mark them as either | |
398 | * found, lost or updated. Update the nodes in the card topology tree | |
399 | * as we go. | |
400 | */ | |
401 | static void | |
83db801c | 402 | update_tree(struct fw_card *card, struct fw_node *root) |
3038e353 KH |
403 | { |
404 | struct list_head list0, list1; | |
405 | struct fw_node *node0, *node1; | |
406 | int i, event; | |
407 | ||
408 | INIT_LIST_HEAD(&list0); | |
409 | list_add_tail(&card->local_node->link, &list0); | |
410 | INIT_LIST_HEAD(&list1); | |
411 | list_add_tail(&root->link, &list1); | |
412 | ||
413 | node0 = fw_node(list0.next); | |
414 | node1 = fw_node(list1.next); | |
3038e353 KH |
415 | |
416 | while (&node0->link != &list0) { | |
417 | ||
418 | /* assert(node0->port_count == node1->port_count); */ | |
419 | if (node0->link_on && !node1->link_on) | |
420 | event = FW_NODE_LINK_OFF; | |
421 | else if (!node0->link_on && node1->link_on) | |
422 | event = FW_NODE_LINK_ON; | |
423 | else | |
424 | event = FW_NODE_UPDATED; | |
425 | ||
426 | node0->node_id = node1->node_id; | |
427 | node0->color = card->color; | |
428 | node0->link_on = node1->link_on; | |
429 | node0->initiated_reset = node1->initiated_reset; | |
83db801c | 430 | node0->max_hops = node1->max_hops; |
3038e353 KH |
431 | node1->color = card->color; |
432 | fw_node_event(card, node0, event); | |
433 | ||
434 | if (card->root_node == node1) | |
435 | card->root_node = node0; | |
436 | if (card->irm_node == node1) | |
437 | card->irm_node = node0; | |
438 | ||
439 | for (i = 0; i < node0->port_count; i++) { | |
440 | if (node0->ports[i].node && node1->ports[i].node) { | |
c781c06d KH |
441 | /* |
442 | * This port didn't change, queue the | |
3038e353 | 443 | * connected node for further |
c781c06d KH |
444 | * investigation. |
445 | */ | |
3038e353 KH |
446 | if (node0->ports[i].node->color == card->color) |
447 | continue; | |
448 | list_add_tail(&node0->ports[i].node->link, | |
449 | &list0); | |
450 | list_add_tail(&node1->ports[i].node->link, | |
451 | &list1); | |
452 | } else if (node0->ports[i].node) { | |
c781c06d KH |
453 | /* |
454 | * The nodes connected here were | |
3038e353 KH |
455 | * unplugged; unref the lost nodes and |
456 | * queue FW_NODE_LOST callbacks for | |
c781c06d KH |
457 | * them. |
458 | */ | |
3038e353 KH |
459 | |
460 | for_each_fw_node(card, node0->ports[i].node, | |
461 | report_lost_node); | |
462 | node0->ports[i].node = NULL; | |
3038e353 | 463 | } else if (node1->ports[i].node) { |
c781c06d KH |
464 | /* |
465 | * One or more node were connected to | |
3038e353 KH |
466 | * this port. Move the new nodes into |
467 | * the tree and queue FW_NODE_CREATED | |
c781c06d KH |
468 | * callbacks for them. |
469 | */ | |
3038e353 KH |
470 | move_tree(node0, node1, i); |
471 | for_each_fw_node(card, node0->ports[i].node, | |
472 | report_found_node); | |
3038e353 KH |
473 | } |
474 | } | |
475 | ||
476 | node0 = fw_node(node0->link.next); | |
477 | node1 = fw_node(node1->link.next); | |
478 | } | |
479 | } | |
480 | ||
473d28c7 KH |
481 | static void |
482 | update_topology_map(struct fw_card *card, u32 *self_ids, int self_id_count) | |
483 | { | |
484 | int node_count; | |
473d28c7 KH |
485 | |
486 | card->topology_map[1]++; | |
487 | node_count = (card->root_node->node_id & 0x3f) + 1; | |
488 | card->topology_map[2] = (node_count << 16) | self_id_count; | |
e175569c | 489 | card->topology_map[0] = (self_id_count + 2) << 16; |
473d28c7 | 490 | memcpy(&card->topology_map[3], self_ids, self_id_count * 4); |
e175569c | 491 | fw_compute_block_crc(card->topology_map); |
473d28c7 KH |
492 | } |
493 | ||
3038e353 KH |
494 | void |
495 | fw_core_handle_bus_reset(struct fw_card *card, | |
496 | int node_id, int generation, | |
497 | int self_id_count, u32 * self_ids) | |
498 | { | |
499 | struct fw_node *local_node; | |
500 | unsigned long flags; | |
3038e353 KH |
501 | |
502 | fw_flush_transactions(card); | |
503 | ||
504 | spin_lock_irqsave(&card->lock, flags); | |
505 | ||
c781c06d KH |
506 | /* |
507 | * If the new topology has a different self_id_count the topology | |
83db801c | 508 | * changed, either nodes were added or removed. In that case we |
c781c06d KH |
509 | * reset the IRM reset counter. |
510 | */ | |
83db801c | 511 | if (card->self_id_count != self_id_count) |
931c4834 | 512 | card->bm_retries = 0; |
83db801c | 513 | |
3038e353 | 514 | card->node_id = node_id; |
3038e353 | 515 | card->generation = generation; |
931c4834 | 516 | card->reset_jiffies = jiffies; |
993baca3 | 517 | schedule_delayed_work(&card->work, 0); |
3038e353 | 518 | |
473d28c7 KH |
519 | local_node = build_tree(card, self_ids, self_id_count); |
520 | ||
521 | update_topology_map(card, self_ids, self_id_count); | |
3038e353 KH |
522 | |
523 | card->color++; | |
524 | ||
525 | if (local_node == NULL) { | |
526 | fw_error("topology build failed\n"); | |
527 | /* FIXME: We need to issue a bus reset in this case. */ | |
528 | } else if (card->local_node == NULL) { | |
529 | card->local_node = local_node; | |
530 | for_each_fw_node(card, local_node, report_found_node); | |
531 | } else { | |
83db801c | 532 | update_tree(card, local_node); |
3038e353 KH |
533 | } |
534 | ||
535 | spin_unlock_irqrestore(&card->lock, flags); | |
536 | } | |
3038e353 | 537 | EXPORT_SYMBOL(fw_core_handle_bus_reset); |