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>
25 #include <asm/system.h>
26 #include "fw-transaction.h"
27 #include "fw-topology.h"
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)
38 #define SELF_ID_EXT_SEQUENCE(q) (((q) >> 20) & 0x07)
40 static u32
*count_ports(u32
*sid
, int *total_port_count
, int *child_port_count
)
43 int port_type
, shift
, seq
;
45 *total_port_count
= 0;
46 *child_port_count
= 0;
53 port_type
= (q
>> shift
) & 0x03;
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
:
66 if (!SELF_ID_MORE_PACKETS(q
))
74 * Check that the extra packets actually are
75 * extended self ID packets and that the
76 * sequence numbers in the extended self ID
77 * packets increase as expected.
80 if (!SELF_ID_EXTENDED(q
) ||
81 seq
!= SELF_ID_EXT_SEQUENCE(q
))
89 static int get_port_type(u32
*sid
, int port_index
)
93 index
= (port_index
+ 5) / 8;
94 shift
= 16 - ((port_index
+ 5) & 7) * 2;
95 return (sid
[index
] >> shift
) & 0x03;
98 static struct fw_node
*fw_node_create(u32 sid
, int port_count
, int color
)
100 struct fw_node
*node
;
102 node
= kzalloc(sizeof(*node
) + port_count
* sizeof(node
->ports
[0]),
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
);
111 node
->port_count
= port_count
;
113 atomic_set(&node
->ref_count
, 1);
114 INIT_LIST_HEAD(&node
->link
);
120 * Compute the maximum hop count for this node and it's children. The
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.
133 static void update_hop_count(struct fw_node
*node
)
135 int depths
[2] = { -1, -1 };
136 int max_child_hops
= 0;
139 for (i
= 0; i
< node
->port_count
; i
++) {
140 if (node
->ports
[i
] == NULL
)
143 if (node
->ports
[i
]->max_hops
> max_child_hops
)
144 max_child_hops
= node
->ports
[i
]->max_hops
;
146 if (node
->ports
[i
]->max_depth
> depths
[0]) {
147 depths
[1] = depths
[0];
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
;
153 node
->max_depth
= depths
[0] + 1;
154 node
->max_hops
= max(max_child_hops
, depths
[0] + depths
[1] + 2);
157 static inline struct fw_node
*fw_node(struct list_head
*l
)
159 return list_entry(l
, struct fw_node
, link
);
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
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
171 * internally consistent. On succcess this function returns the
172 * fw_node corresponding to the local card otherwise NULL.
174 static struct fw_node
*build_tree(struct fw_card
*card
,
175 u32
*sid
, int self_id_count
)
177 struct fw_node
*node
, *child
, *local_node
, *irm_node
;
178 struct list_head stack
, *h
;
179 u32
*next_sid
, *end
, q
;
180 int i
, port_count
, child_port_count
, phy_id
, parent_count
, stack_depth
;
182 bool beta_repeaters_present
;
186 INIT_LIST_HEAD(&stack
);
188 end
= sid
+ self_id_count
;
191 gap_count
= SELF_ID_GAP_COUNT(*sid
);
192 beta_repeaters_present
= false;
195 next_sid
= count_ports(sid
, &port_count
, &child_port_count
);
197 if (next_sid
== NULL
) {
198 fw_error("Inconsistent extended self IDs.\n");
203 if (phy_id
!= SELF_ID_PHY_ID(q
)) {
204 fw_error("PHY ID mismatch in self ID: %d != %d.\n",
205 phy_id
, SELF_ID_PHY_ID(q
));
209 if (child_port_count
> stack_depth
) {
210 fw_error("Topology stack underflow\n");
215 * Seek back from the top of our stack to find the
216 * start of the child nodes for this node.
218 for (i
= 0, h
= &stack
; i
< child_port_count
; i
++)
221 * When the stack is empty, this yields an invalid value,
222 * but that pointer will never be dereferenced.
226 node
= fw_node_create(q
, port_count
, card
->color
);
228 fw_error("Out of memory while building topology.\n");
232 if (phy_id
== (card
->node_id
& 0x3f))
235 if (SELF_ID_CONTENDER(q
))
240 for (i
= 0; i
< port_count
; i
++) {
241 switch (get_port_type(sid
, i
)) {
242 case SELFID_PORT_PARENT
:
244 * Who's your daddy? We dont know the
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
257 case SELFID_PORT_CHILD
:
258 node
->ports
[i
] = child
;
260 * Fix up parent reference for this
263 child
->ports
[child
->color
] = node
;
264 child
->color
= card
->color
;
265 child
= fw_node(child
->link
.next
);
271 * Check that the node reports exactly one parent
272 * port, except for the root, which of course should
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
);
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
;
287 if (node
->phy_speed
== SCODE_BETA
&&
288 parent_count
+ child_port_count
> 1)
289 beta_repeaters_present
= true;
292 * If all PHYs does not report the same gap count
293 * setting, we fall back to 63 which will force a gap
294 * count reconfiguration and a reset.
296 if (SELF_ID_GAP_COUNT(q
) != gap_count
)
299 update_hop_count(node
);
305 card
->root_node
= node
;
306 card
->irm_node
= irm_node
;
307 card
->gap_count
= gap_count
;
308 card
->beta_repeaters_present
= beta_repeaters_present
;
313 typedef void (*fw_node_callback_t
)(struct fw_card
* card
,
314 struct fw_node
* node
,
315 struct fw_node
* parent
);
318 for_each_fw_node(struct fw_card
*card
, struct fw_node
*root
,
319 fw_node_callback_t callback
)
321 struct list_head list
;
322 struct fw_node
*node
, *next
, *child
, *parent
;
325 INIT_LIST_HEAD(&list
);
328 list_add_tail(&root
->link
, &list
);
330 list_for_each_entry(node
, &list
, link
) {
331 node
->color
= card
->color
;
333 for (i
= 0; i
< node
->port_count
; i
++) {
334 child
= node
->ports
[i
];
337 if (child
->color
== card
->color
)
341 list_add_tail(&child
->link
, &list
);
345 callback(card
, node
, parent
);
348 list_for_each_entry_safe(node
, next
, &list
, link
)
353 report_lost_node(struct fw_card
*card
,
354 struct fw_node
*node
, struct fw_node
*parent
)
356 fw_node_event(card
, node
, FW_NODE_DESTROYED
);
361 report_found_node(struct fw_card
*card
,
362 struct fw_node
*node
, struct fw_node
*parent
)
364 int b_path
= (node
->phy_speed
== SCODE_BETA
);
366 if (parent
!= NULL
) {
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
;
370 node
->b_path
= parent
->b_path
&& b_path
;
372 node
->max_speed
= node
->phy_speed
;
373 node
->b_path
= b_path
;
376 fw_node_event(card
, node
, FW_NODE_CREATED
);
379 void fw_destroy_nodes(struct fw_card
*card
)
383 spin_lock_irqsave(&card
->lock
, flags
);
385 if (card
->local_node
!= NULL
)
386 for_each_fw_node(card
, card
->local_node
, report_lost_node
);
387 card
->local_node
= NULL
;
388 spin_unlock_irqrestore(&card
->lock
, flags
);
391 static void move_tree(struct fw_node
*node0
, struct fw_node
*node1
, int port
)
393 struct fw_node
*tree
;
396 tree
= node1
->ports
[port
];
397 node0
->ports
[port
] = tree
;
398 for (i
= 0; i
< tree
->port_count
; i
++) {
399 if (tree
->ports
[i
] == node1
) {
400 tree
->ports
[i
] = node0
;
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
413 update_tree(struct fw_card
*card
, struct fw_node
*root
)
415 struct list_head list0
, list1
;
416 struct fw_node
*node0
, *node1
;
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
);
424 node0
= fw_node(list0
.next
);
425 node1
= fw_node(list1
.next
);
427 while (&node0
->link
!= &list0
) {
428 WARN_ON(node0
->port_count
!= node1
->port_count
);
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
;
435 event
= FW_NODE_UPDATED
;
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
;
441 node0
->max_hops
= node1
->max_hops
;
442 node1
->color
= card
->color
;
443 fw_node_event(card
, node0
, event
);
445 if (card
->root_node
== node1
)
446 card
->root_node
= node0
;
447 if (card
->irm_node
== node1
)
448 card
->irm_node
= node0
;
450 for (i
= 0; i
< node0
->port_count
; i
++) {
451 if (node0
->ports
[i
] && node1
->ports
[i
]) {
453 * This port didn't change, queue the
454 * connected node for further
457 if (node0
->ports
[i
]->color
== card
->color
)
459 list_add_tail(&node0
->ports
[i
]->link
, &list0
);
460 list_add_tail(&node1
->ports
[i
]->link
, &list1
);
461 } else if (node0
->ports
[i
]) {
463 * The nodes connected here were
464 * unplugged; unref the lost nodes and
465 * queue FW_NODE_LOST callbacks for
469 for_each_fw_node(card
, node0
->ports
[i
],
471 node0
->ports
[i
] = NULL
;
472 } else if (node1
->ports
[i
]) {
474 * One or more node were connected to
475 * this port. Move the new nodes into
476 * the tree and queue FW_NODE_CREATED
477 * callbacks for them.
479 move_tree(node0
, node1
, i
);
480 for_each_fw_node(card
, node0
->ports
[i
],
485 node0
= fw_node(node0
->link
.next
);
486 node1
= fw_node(node1
->link
.next
);
491 update_topology_map(struct fw_card
*card
, u32
*self_ids
, int self_id_count
)
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
;
498 card
->topology_map
[0] = (self_id_count
+ 2) << 16;
499 memcpy(&card
->topology_map
[3], self_ids
, self_id_count
* 4);
500 fw_compute_block_crc(card
->topology_map
);
504 fw_core_handle_bus_reset(struct fw_card
*card
,
505 int node_id
, int generation
,
506 int self_id_count
, u32
* self_ids
)
508 struct fw_node
*local_node
;
511 fw_flush_transactions(card
);
513 spin_lock_irqsave(&card
->lock
, flags
);
516 * If the new topology has a different self_id_count the topology
517 * changed, either nodes were added or removed. In that case we
518 * reset the IRM reset counter.
520 if (card
->self_id_count
!= self_id_count
)
521 card
->bm_retries
= 0;
523 card
->node_id
= node_id
;
525 * Update node_id before generation to prevent anybody from using
526 * a stale node_id together with a current generation.
529 card
->generation
= generation
;
530 card
->reset_jiffies
= jiffies
;
531 schedule_delayed_work(&card
->work
, 0);
533 local_node
= build_tree(card
, self_ids
, self_id_count
);
535 update_topology_map(card
, self_ids
, self_id_count
);
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
);
546 update_tree(card
, local_node
);
549 spin_unlock_irqrestore(&card
->lock
, flags
);
551 EXPORT_SYMBOL(fw_core_handle_bus_reset
);