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