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