2 * Incremental bus scan, based on bus topology
4 * Copyright (C) 2004-2006 Kristian Hoegsberg <krh@bitplanet.net>
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.
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.
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.
21 #include <linux/module.h>
22 #include <linux/wait.h>
23 #include <linux/errno.h>
24 #include <asm/system.h>
25 #include "fw-transaction.h"
26 #include "fw-topology.h"
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)
37 #define SELF_ID_EXT_SEQUENCE(q) (((q) >> 20) & 0x07)
39 static u32
*count_ports(u32
*sid
, int *total_port_count
, int *child_port_count
)
42 int port_type
, shift
, seq
;
44 *total_port_count
= 0;
45 *child_port_count
= 0;
52 port_type
= (q
>> shift
) & 0x03;
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
:
65 if (!SELF_ID_MORE_PACKETS(q
))
73 * Check that the extra packets actually are
74 * extended self ID packets and that the
75 * sequence numbers in the extended self ID
76 * packets increase as expected.
79 if (!SELF_ID_EXTENDED(q
) ||
80 seq
!= SELF_ID_EXT_SEQUENCE(q
))
88 static int get_port_type(u32
*sid
, int port_index
)
92 index
= (port_index
+ 5) / 8;
93 shift
= 16 - ((port_index
+ 5) & 7) * 2;
94 return (sid
[index
] >> shift
) & 0x03;
97 static struct fw_node
*fw_node_create(u32 sid
, int port_count
, int color
)
101 node
= kzalloc(sizeof(*node
) + port_count
* sizeof(node
->ports
[0]),
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
);
110 node
->port_count
= port_count
;
112 atomic_set(&node
->ref_count
, 1);
113 INIT_LIST_HEAD(&node
->link
);
119 * Compute the maximum hop count for this node and it's children. The
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.
132 static void update_hop_count(struct fw_node
*node
)
134 int depths
[2] = { -1, -1 };
135 int max_child_hops
= 0;
138 for (i
= 0; i
< node
->port_count
; i
++) {
139 if (node
->ports
[i
] == NULL
)
142 if (node
->ports
[i
]->max_hops
> max_child_hops
)
143 max_child_hops
= node
->ports
[i
]->max_hops
;
145 if (node
->ports
[i
]->max_depth
> depths
[0]) {
146 depths
[1] = depths
[0];
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
;
152 node
->max_depth
= depths
[0] + 1;
153 node
->max_hops
= max(max_child_hops
, depths
[0] + depths
[1] + 2);
156 static inline struct fw_node
*fw_node(struct list_head
*l
)
158 return list_entry(l
, struct fw_node
, link
);
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
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
170 * internally consistent. On succcess this function returns the
171 * fw_node corresponding to the local card otherwise NULL.
173 static struct fw_node
*build_tree(struct fw_card
*card
,
174 u32
*sid
, int self_id_count
)
176 struct fw_node
*node
, *child
, *local_node
, *irm_node
;
177 struct list_head stack
, *h
;
178 u32
*next_sid
, *end
, q
;
179 int i
, port_count
, child_port_count
, phy_id
, parent_count
, stack_depth
;
181 bool beta_repeaters_present
;
185 INIT_LIST_HEAD(&stack
);
187 end
= sid
+ self_id_count
;
190 gap_count
= SELF_ID_GAP_COUNT(*sid
);
191 beta_repeaters_present
= false;
194 next_sid
= count_ports(sid
, &port_count
, &child_port_count
);
196 if (next_sid
== NULL
) {
197 fw_error("Inconsistent extended self IDs.\n");
202 if (phy_id
!= SELF_ID_PHY_ID(q
)) {
203 fw_error("PHY ID mismatch in self ID: %d != %d.\n",
204 phy_id
, SELF_ID_PHY_ID(q
));
208 if (child_port_count
> stack_depth
) {
209 fw_error("Topology stack underflow\n");
214 * Seek back from the top of our stack to find the
215 * start of the child nodes for this node.
217 for (i
= 0, h
= &stack
; i
< child_port_count
; i
++)
220 * When the stack is empty, this yields an invalid value,
221 * but that pointer will never be dereferenced.
225 node
= fw_node_create(q
, port_count
, card
->color
);
227 fw_error("Out of memory while building topology.\n");
231 if (phy_id
== (card
->node_id
& 0x3f))
234 if (SELF_ID_CONTENDER(q
))
239 for (i
= 0; i
< port_count
; i
++) {
240 switch (get_port_type(sid
, i
)) {
241 case SELFID_PORT_PARENT
:
243 * Who's your daddy? We dont know the
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
256 case SELFID_PORT_CHILD
:
257 node
->ports
[i
] = child
;
259 * Fix up parent reference for this
262 child
->ports
[child
->color
] = node
;
263 child
->color
= card
->color
;
264 child
= fw_node(child
->link
.next
);
270 * Check that the node reports exactly one parent
271 * port, except for the root, which of course should
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
);
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
;
286 if (node
->phy_speed
== SCODE_BETA
&&
287 parent_count
+ child_port_count
> 1)
288 beta_repeaters_present
= true;
291 * If all PHYs does not report the same gap count
292 * setting, we fall back to 63 which will force a gap
293 * count reconfiguration and a reset.
295 if (SELF_ID_GAP_COUNT(q
) != gap_count
)
298 update_hop_count(node
);
304 card
->root_node
= node
;
305 card
->irm_node
= irm_node
;
306 card
->gap_count
= gap_count
;
307 card
->beta_repeaters_present
= beta_repeaters_present
;
312 typedef void (*fw_node_callback_t
)(struct fw_card
* card
,
313 struct fw_node
* node
,
314 struct fw_node
* parent
);
317 for_each_fw_node(struct fw_card
*card
, struct fw_node
*root
,
318 fw_node_callback_t callback
)
320 struct list_head list
;
321 struct fw_node
*node
, *next
, *child
, *parent
;
324 INIT_LIST_HEAD(&list
);
327 list_add_tail(&root
->link
, &list
);
329 list_for_each_entry(node
, &list
, link
) {
330 node
->color
= card
->color
;
332 for (i
= 0; i
< node
->port_count
; i
++) {
333 child
= node
->ports
[i
];
336 if (child
->color
== card
->color
)
340 list_add_tail(&child
->link
, &list
);
344 callback(card
, node
, parent
);
347 list_for_each_entry_safe(node
, next
, &list
, link
)
352 report_lost_node(struct fw_card
*card
,
353 struct fw_node
*node
, struct fw_node
*parent
)
355 fw_node_event(card
, node
, FW_NODE_DESTROYED
);
360 report_found_node(struct fw_card
*card
,
361 struct fw_node
*node
, struct fw_node
*parent
)
363 int b_path
= (node
->phy_speed
== SCODE_BETA
);
365 if (parent
!= NULL
) {
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
;
369 node
->b_path
= parent
->b_path
&& b_path
;
371 node
->max_speed
= node
->phy_speed
;
372 node
->b_path
= b_path
;
375 fw_node_event(card
, node
, FW_NODE_CREATED
);
378 void fw_destroy_nodes(struct fw_card
*card
)
382 spin_lock_irqsave(&card
->lock
, flags
);
384 if (card
->local_node
!= NULL
)
385 for_each_fw_node(card
, card
->local_node
, report_lost_node
);
386 card
->local_node
= NULL
;
387 spin_unlock_irqrestore(&card
->lock
, flags
);
390 static void move_tree(struct fw_node
*node0
, struct fw_node
*node1
, int port
)
392 struct fw_node
*tree
;
395 tree
= node1
->ports
[port
];
396 node0
->ports
[port
] = tree
;
397 for (i
= 0; i
< tree
->port_count
; i
++) {
398 if (tree
->ports
[i
] == node1
) {
399 tree
->ports
[i
] = node0
;
406 * update_tree - compare the old topology tree for card with the new
407 * one specified by root. Queue the nodes and mark them as either
408 * found, lost or updated. Update the nodes in the card topology tree
412 update_tree(struct fw_card
*card
, struct fw_node
*root
)
414 struct list_head list0
, list1
;
415 struct fw_node
*node0
, *node1
;
418 INIT_LIST_HEAD(&list0
);
419 list_add_tail(&card
->local_node
->link
, &list0
);
420 INIT_LIST_HEAD(&list1
);
421 list_add_tail(&root
->link
, &list1
);
423 node0
= fw_node(list0
.next
);
424 node1
= fw_node(list1
.next
);
426 while (&node0
->link
!= &list0
) {
428 /* assert(node0->port_count == node1->port_count); */
429 if (node0
->link_on
&& !node1
->link_on
)
430 event
= FW_NODE_LINK_OFF
;
431 else if (!node0
->link_on
&& node1
->link_on
)
432 event
= FW_NODE_LINK_ON
;
434 event
= FW_NODE_UPDATED
;
436 node0
->node_id
= node1
->node_id
;
437 node0
->color
= card
->color
;
438 node0
->link_on
= node1
->link_on
;
439 node0
->initiated_reset
= node1
->initiated_reset
;
440 node0
->max_hops
= node1
->max_hops
;
441 node1
->color
= card
->color
;
442 fw_node_event(card
, node0
, event
);
444 if (card
->root_node
== node1
)
445 card
->root_node
= node0
;
446 if (card
->irm_node
== node1
)
447 card
->irm_node
= node0
;
449 for (i
= 0; i
< node0
->port_count
; i
++) {
450 if (node0
->ports
[i
] && node1
->ports
[i
]) {
452 * This port didn't change, queue the
453 * connected node for further
456 if (node0
->ports
[i
]->color
== card
->color
)
458 list_add_tail(&node0
->ports
[i
]->link
, &list0
);
459 list_add_tail(&node1
->ports
[i
]->link
, &list1
);
460 } else if (node0
->ports
[i
]) {
462 * The nodes connected here were
463 * unplugged; unref the lost nodes and
464 * queue FW_NODE_LOST callbacks for
468 for_each_fw_node(card
, node0
->ports
[i
],
470 node0
->ports
[i
] = NULL
;
471 } else if (node1
->ports
[i
]) {
473 * One or more node were connected to
474 * this port. Move the new nodes into
475 * the tree and queue FW_NODE_CREATED
476 * callbacks for them.
478 move_tree(node0
, node1
, i
);
479 for_each_fw_node(card
, node0
->ports
[i
],
484 node0
= fw_node(node0
->link
.next
);
485 node1
= fw_node(node1
->link
.next
);
490 update_topology_map(struct fw_card
*card
, u32
*self_ids
, int self_id_count
)
494 card
->topology_map
[1]++;
495 node_count
= (card
->root_node
->node_id
& 0x3f) + 1;
496 card
->topology_map
[2] = (node_count
<< 16) | self_id_count
;
497 card
->topology_map
[0] = (self_id_count
+ 2) << 16;
498 memcpy(&card
->topology_map
[3], self_ids
, self_id_count
* 4);
499 fw_compute_block_crc(card
->topology_map
);
503 fw_core_handle_bus_reset(struct fw_card
*card
,
504 int node_id
, int generation
,
505 int self_id_count
, u32
* self_ids
)
507 struct fw_node
*local_node
;
510 fw_flush_transactions(card
);
512 spin_lock_irqsave(&card
->lock
, flags
);
515 * If the new topology has a different self_id_count the topology
516 * changed, either nodes were added or removed. In that case we
517 * reset the IRM reset counter.
519 if (card
->self_id_count
!= self_id_count
)
520 card
->bm_retries
= 0;
522 card
->node_id
= node_id
;
524 * Update node_id before generation to prevent anybody from using
525 * a stale node_id together with a current generation.
528 card
->generation
= generation
;
529 card
->reset_jiffies
= jiffies
;
530 schedule_delayed_work(&card
->work
, 0);
532 local_node
= build_tree(card
, self_ids
, self_id_count
);
534 update_topology_map(card
, self_ids
, self_id_count
);
538 if (local_node
== NULL
) {
539 fw_error("topology build failed\n");
540 /* FIXME: We need to issue a bus reset in this case. */
541 } else if (card
->local_node
== NULL
) {
542 card
->local_node
= local_node
;
543 for_each_fw_node(card
, local_node
, report_found_node
);
545 update_tree(card
, local_node
);
548 spin_unlock_irqrestore(&card
->lock
, flags
);
550 EXPORT_SYMBOL(fw_core_handle_bus_reset
);