1/*- 2 * This file is provided under a dual BSD/GPLv2 license. When using or 3 * redistributing this file, you may do so under either license. 4 * 5 * GPL LICENSE SUMMARY 6 * 7 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved. 8 * 9 * This program is free software; you can redistribute it and/or modify 10 * it under the terms of version 2 of the GNU General Public License as 11 * published by the Free Software Foundation. 12 * 13 * This program is distributed in the hope that it will be useful, but 14 * WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 * General Public License for more details. 17 * 18 * You should have received a copy of the GNU General Public License 19 * along with this program; if not, write to the Free Software 20 * Foundation, Inc., 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA. 21 * The full GNU General Public License is included in this distribution 22 * in the file called LICENSE.GPL. 23 * 24 * BSD LICENSE 25 * 26 * Copyright(c) 2008 - 2011 Intel Corporation. All rights reserved. 27 * All rights reserved. 28 * 29 * Redistribution and use in source and binary forms, with or without 30 * modification, are permitted provided that the following conditions 31 * are met: 32 * 33 * * Redistributions of source code must retain the above copyright 34 * notice, this list of conditions and the following disclaimer. 35 * * Redistributions in binary form must reproduce the above copyright 36 * notice, this list of conditions and the following disclaimer in 37 * the documentation and/or other materials provided with the 38 * distribution. 39 * 40 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 41 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 42 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 43 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 44 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 45 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 46 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 47 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 48 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 49 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 50 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 51 */ 52 53#include <sys/cdefs.h> 54__FBSDID("$FreeBSD$"); 55 56/** 57 * @file 58 * 59 * @brief This file contains the implementation of the 60 * SCIC_SDS_REMOTE_NODE_TABLE public, protected, and private methods. 61 */ 62 63#include <dev/isci/scil/scic_sds_remote_node_table.h> 64#include <dev/isci/scil/scic_sds_remote_node_context.h> 65 66/** 67 * This routine will find the bit position in absolute bit terms of the next 68 * available bit for selection. The absolute bit is index * 32 + bit 69 * position. If there are available bits in the first U32 then it is just bit 70 * position. 71 * @param[in] remote_node_table This is the remote node index table from 72 * which the selection will be made. 73 * @param[in] group_table_index This is the index to the group table from 74 * which to search for an available selection. 75 * 76 * @return U32 This is the absolute bit position for an available group. 77 */ 78static 79U32 scic_sds_remote_node_table_get_group_index( 80 SCIC_REMOTE_NODE_TABLE_T * remote_node_table, 81 U32 group_table_index 82) 83{ 84 U32 dword_index; 85 U32 * group_table; 86 U32 bit_index; 87 88 group_table = remote_node_table->remote_node_groups[group_table_index]; 89 90 for (dword_index = 0; dword_index < remote_node_table->group_array_size; dword_index++) 91 { 92 if (group_table[dword_index] != 0) 93 { 94 for (bit_index = 0; bit_index < 32; bit_index++) 95 { 96 if ((group_table[dword_index] & (1 << bit_index)) != 0) 97 { 98 return (dword_index * 32) + bit_index; 99 } 100 } 101 } 102 } 103 104 return SCIC_SDS_REMOTE_NODE_TABLE_INVALID_INDEX; 105} 106 107/** 108 * This method will clear the group index entry in the specified group index 109 * table. 110 * 111 * @param[in out] remote_node_table This the remote node table in which to 112 * clear the selector. 113 * @param[in] set_index This is the remote node selector in which the change 114 * will be made. 115 * @param[in] group_index This is the bit index in the table to be modified. 116 * 117 * @return none 118 */ 119static 120void scic_sds_remote_node_table_clear_group_index( 121 SCIC_REMOTE_NODE_TABLE_T * remote_node_table, 122 U32 group_table_index, 123 U32 group_index 124) 125{ 126 U32 dword_index; 127 U32 bit_index; 128 U32 * group_table; 129 130 ASSERT(group_table_index < SCU_STP_REMOTE_NODE_COUNT); 131 ASSERT(group_index < (U32)(remote_node_table->group_array_size * 32)); 132 133 dword_index = group_index / 32; 134 bit_index = group_index % 32; 135 group_table = remote_node_table->remote_node_groups[group_table_index]; 136 137 group_table[dword_index] = group_table[dword_index] & ~(1 << bit_index); 138} 139 140/** 141 * This method will set the group index bit entry in the specified gropu index 142 * table. 143 * 144 * @param[in out] remote_node_table This the remote node table in which to set 145 * the selector. 146 * @param[in] group_table_index This is the remote node selector in which the 147 * change will be made. 148 * @param[in] group_index This is the bit position in the table to be 149 * modified. 150 * 151 * @return none 152 */ 153static 154void scic_sds_remote_node_table_set_group_index( 155 SCIC_REMOTE_NODE_TABLE_T * remote_node_table, 156 U32 group_table_index, 157 U32 group_index 158) 159{ 160 U32 dword_index; 161 U32 bit_index; 162 U32 * group_table; 163 164 ASSERT(group_table_index < SCU_STP_REMOTE_NODE_COUNT); 165 ASSERT(group_index < (U32)(remote_node_table->group_array_size * 32)); 166 167 dword_index = group_index / 32; 168 bit_index = group_index % 32; 169 group_table = remote_node_table->remote_node_groups[group_table_index]; 170 171 group_table[dword_index] = group_table[dword_index] | (1 << bit_index); 172} 173 174/** 175 * This method will set the remote to available in the remote node allocation 176 * table. 177 * 178 * @param[in out] remote_node_table This is the remote node table in which to 179 * modify the remote node availability. 180 * @param[in] remote_node_index This is the remote node index that is being 181 * returned to the table. 182 * 183 * @return none 184 */ 185static 186void scic_sds_remote_node_table_set_node_index( 187 SCIC_REMOTE_NODE_TABLE_T * remote_node_table, 188 U32 remote_node_index 189) 190{ 191 U32 dword_location; 192 U32 dword_remainder; 193 U32 slot_normalized; 194 U32 slot_position; 195 196 ASSERT( 197 (remote_node_table->available_nodes_array_size * SCIC_SDS_REMOTE_NODE_SETS_PER_DWORD) 198 > (remote_node_index / SCU_STP_REMOTE_NODE_COUNT) 199 ); 200 201 dword_location = remote_node_index / SCIC_SDS_REMOTE_NODES_PER_DWORD; 202 dword_remainder = remote_node_index % SCIC_SDS_REMOTE_NODES_PER_DWORD; 203 slot_normalized = (dword_remainder / SCU_STP_REMOTE_NODE_COUNT) * sizeof(U32); 204 slot_position = remote_node_index % SCU_STP_REMOTE_NODE_COUNT; 205 206 remote_node_table->available_remote_nodes[dword_location] |= 207 1 << (slot_normalized + slot_position); 208} 209 210/** 211 * This method clears the remote node index from the table of available remote 212 * nodes. 213 * 214 * @param[in out] remote_node_table This is the remote node table from which 215 * to clear the available remote node bit. 216 * @param[in] remote_node_index This is the remote node index which is to be 217 * cleared from the table. 218 * 219 * @return none 220 */ 221static 222void scic_sds_remote_node_table_clear_node_index( 223 SCIC_REMOTE_NODE_TABLE_T * remote_node_table, 224 U32 remote_node_index 225) 226{ 227 U32 dword_location; 228 U32 dword_remainder; 229 U32 slot_position; 230 U32 slot_normalized; 231 232 ASSERT( 233 (remote_node_table->available_nodes_array_size * SCIC_SDS_REMOTE_NODE_SETS_PER_DWORD) 234 > (remote_node_index / SCU_STP_REMOTE_NODE_COUNT) 235 ); 236 237 dword_location = remote_node_index / SCIC_SDS_REMOTE_NODES_PER_DWORD; 238 dword_remainder = remote_node_index % SCIC_SDS_REMOTE_NODES_PER_DWORD; 239 slot_normalized = (dword_remainder / SCU_STP_REMOTE_NODE_COUNT) * sizeof(U32); 240 slot_position = remote_node_index % SCU_STP_REMOTE_NODE_COUNT; 241 242 remote_node_table->available_remote_nodes[dword_location] &= 243 ~(1 << (slot_normalized + slot_position)); 244} 245 246/** 247 * This method clears the entire table slot at the specified slot index. 248 * 249 * @param[in out] remote_node_table The remote node table from which the slot 250 * will be cleared. 251 * @param[in] group_index The index for the slot that is to be cleared. 252 * 253 * @return none 254 */ 255static 256void scic_sds_remote_node_table_clear_group( 257 SCIC_REMOTE_NODE_TABLE_T * remote_node_table, 258 U32 group_index 259) 260{ 261 U32 dword_location; 262 U32 dword_remainder; 263 U32 dword_value; 264 265 ASSERT( 266 (remote_node_table->available_nodes_array_size * SCIC_SDS_REMOTE_NODE_SETS_PER_DWORD) 267 > (group_index / SCU_STP_REMOTE_NODE_COUNT) 268 ); 269 270 dword_location = group_index / SCIC_SDS_REMOTE_NODE_SETS_PER_DWORD; 271 dword_remainder = group_index % SCIC_SDS_REMOTE_NODE_SETS_PER_DWORD; 272 273 dword_value = remote_node_table->available_remote_nodes[dword_location]; 274 dword_value &= ~(SCIC_SDS_REMOTE_NODE_TABLE_FULL_SLOT_VALUE << (dword_remainder * 4)); 275 remote_node_table->available_remote_nodes[dword_location] = dword_value; 276} 277 278/** 279 * THis method sets an entire remote node group in the remote node table. 280 * 281 * @param[in] remote_node_table 282 * @param[in] group_index 283 */ 284static 285void scic_sds_remote_node_table_set_group( 286 SCIC_REMOTE_NODE_TABLE_T * remote_node_table, 287 U32 group_index 288) 289{ 290 U32 dword_location; 291 U32 dword_remainder; 292 U32 dword_value; 293 294 ASSERT( 295 (remote_node_table->available_nodes_array_size * SCIC_SDS_REMOTE_NODE_SETS_PER_DWORD) 296 > (group_index / SCU_STP_REMOTE_NODE_COUNT) 297 ); 298 299 dword_location = group_index / SCIC_SDS_REMOTE_NODE_SETS_PER_DWORD; 300 dword_remainder = group_index % SCIC_SDS_REMOTE_NODE_SETS_PER_DWORD; 301 302 dword_value = remote_node_table->available_remote_nodes[dword_location]; 303 dword_value |= (SCIC_SDS_REMOTE_NODE_TABLE_FULL_SLOT_VALUE << (dword_remainder * 4)); 304 remote_node_table->available_remote_nodes[dword_location] = dword_value; 305} 306 307/** 308 * This method will return the group value for the specified group index. 309 * 310 * @param[in] remote_node_table This is the remote node table that for which 311 * the group value is to be returned. 312 * @param[in] group_index This is the group index to use to find the group 313 * value. 314 * 315 * @return The bit values at the specified remote node group index. 316 */ 317static 318U8 scic_sds_remote_node_table_get_group_value( 319 SCIC_REMOTE_NODE_TABLE_T * remote_node_table, 320 U32 group_index 321) 322{ 323 U32 dword_location; 324 U32 dword_remainder; 325 U32 dword_value; 326 327 dword_location = group_index / SCIC_SDS_REMOTE_NODE_SETS_PER_DWORD; 328 dword_remainder = group_index % SCIC_SDS_REMOTE_NODE_SETS_PER_DWORD; 329 330 dword_value = remote_node_table->available_remote_nodes[dword_location]; 331 dword_value &= (SCIC_SDS_REMOTE_NODE_TABLE_FULL_SLOT_VALUE << (dword_remainder * 4)); 332 dword_value = dword_value >> (dword_remainder * 4); 333 334 return (U8)dword_value; 335} 336 337/** 338 * This method will initialize the remote node table for use. 339 * 340 * @param[in out] remote_node_table The remote that which is to be 341 * initialized. 342 * @param[in] remote_node_entries The number of entries to put in the table. 343 * 344 * @return none 345 */ 346void scic_sds_remote_node_table_initialize( 347 SCIC_REMOTE_NODE_TABLE_T * remote_node_table, 348 U32 remote_node_entries 349) 350{ 351 U32 index; 352 353 // Initialize the raw data we could improve the speed by only initializing 354 // those entries that we are actually going to be used 355 memset( 356 remote_node_table->available_remote_nodes, 357 0x00, 358 sizeof(remote_node_table->available_remote_nodes) 359 ); 360 361 memset( 362 remote_node_table->remote_node_groups, 363 0x00, 364 sizeof(remote_node_table->remote_node_groups) 365 ); 366 367 // Initialize the available remote node sets 368 remote_node_table->available_nodes_array_size = (U16) 369 (remote_node_entries / SCIC_SDS_REMOTE_NODES_PER_DWORD) 370 + ((remote_node_entries % SCIC_SDS_REMOTE_NODES_PER_DWORD) != 0); 371 372 373 // Initialize each full DWORD to a FULL SET of remote nodes 374 for (index = 0; index < remote_node_entries; index++) 375 { 376 scic_sds_remote_node_table_set_node_index(remote_node_table, index); 377 } 378 379 remote_node_table->group_array_size = (U16) 380 (remote_node_entries / (SCU_STP_REMOTE_NODE_COUNT * 32)) 381 + ((remote_node_entries % (SCU_STP_REMOTE_NODE_COUNT * 32)) != 0); 382 383 for (index = 0; index < (remote_node_entries / SCU_STP_REMOTE_NODE_COUNT); index++) 384 { 385 // These are all guaranteed to be full slot values so fill them in the 386 // available sets of 3 remote nodes 387 scic_sds_remote_node_table_set_group_index(remote_node_table, 2, index); 388 } 389 390 // Now fill in any remainders that we may find 391 if ((remote_node_entries % SCU_STP_REMOTE_NODE_COUNT) == 2) 392 { 393 scic_sds_remote_node_table_set_group_index(remote_node_table, 1, index); 394 } 395 else if ((remote_node_entries % SCU_STP_REMOTE_NODE_COUNT) == 1) 396 { 397 scic_sds_remote_node_table_set_group_index(remote_node_table, 0, index); 398 } 399} 400 401/** 402 * This method will allocate a single RNi from the remote node table. The 403 * table index will determine from which remote node group table to search. 404 * This search may fail and another group node table can be specified. The 405 * function is designed to allow a serach of the available single remote node 406 * group up to the triple remote node group. If an entry is found in the 407 * specified table the remote node is removed and the remote node groups are 408 * updated. 409 * 410 * @param[in out] remote_node_table The remote node table from which to 411 * allocate a remote node. 412 * @param[in] table_index The group index that is to be used for the search. 413 * 414 * @return The RNi value or an invalid remote node context if an RNi can not 415 * be found. 416 */ 417static 418U16 scic_sds_remote_node_table_allocate_single_remote_node( 419 SCIC_REMOTE_NODE_TABLE_T * remote_node_table, 420 U32 group_table_index 421) 422{ 423 U8 index; 424 U8 group_value; 425 U32 group_index; 426 U16 remote_node_index = SCIC_SDS_REMOTE_NODE_CONTEXT_INVALID_INDEX; 427 428 group_index = scic_sds_remote_node_table_get_group_index( 429 remote_node_table, group_table_index); 430 431 // We could not find an available slot in the table selector 0 432 if (group_index != SCIC_SDS_REMOTE_NODE_TABLE_INVALID_INDEX) 433 { 434 group_value = scic_sds_remote_node_table_get_group_value( 435 remote_node_table, group_index); 436 437 for (index = 0; index < SCU_STP_REMOTE_NODE_COUNT; index++) 438 { 439 if (((1 << index) & group_value) != 0) 440 { 441 // We have selected a bit now clear it 442 remote_node_index = (U16) (group_index * SCU_STP_REMOTE_NODE_COUNT 443 + index); 444 445 scic_sds_remote_node_table_clear_group_index( 446 remote_node_table, group_table_index, group_index 447 ); 448 449 scic_sds_remote_node_table_clear_node_index( 450 remote_node_table, remote_node_index 451 ); 452 453 if (group_table_index > 0) 454 { 455 scic_sds_remote_node_table_set_group_index( 456 remote_node_table, group_table_index - 1, group_index 457 ); 458 } 459 460 break; 461 } 462 } 463 } 464 465 return remote_node_index; 466} 467 468/** 469 * This method will allocate three consecutive remote node context entries. If 470 * there are no remaining triple entries the function will return a failure. 471 * 472 * @param[in] remote_node_table This is the remote node table from which to 473 * allocate the remote node entries. 474 * @param[in] group_table_index THis is the group table index which must equal 475 * two (2) for this operation. 476 * 477 * @return The remote node index that represents three consecutive remote node 478 * entries or an invalid remote node context if none can be found. 479 */ 480static 481U16 scic_sds_remote_node_table_allocate_triple_remote_node( 482 SCIC_REMOTE_NODE_TABLE_T * remote_node_table, 483 U32 group_table_index 484) 485{ 486 U32 group_index; 487 U16 remote_node_index = SCIC_SDS_REMOTE_NODE_CONTEXT_INVALID_INDEX; 488 489 group_index = scic_sds_remote_node_table_get_group_index( 490 remote_node_table, group_table_index); 491 492 if (group_index != SCIC_SDS_REMOTE_NODE_TABLE_INVALID_INDEX) 493 { 494 remote_node_index = (U16) group_index * SCU_STP_REMOTE_NODE_COUNT; 495 496 scic_sds_remote_node_table_clear_group_index( 497 remote_node_table, group_table_index, group_index 498 ); 499 500 scic_sds_remote_node_table_clear_group( 501 remote_node_table, group_index 502 ); 503 } 504 505 return remote_node_index; 506} 507 508/** 509 * This method will allocate a remote node that mataches the remote node count 510 * specified by the caller. Valid values for remote node count is 511 * SCU_SSP_REMOTE_NODE_COUNT(1) or SCU_STP_REMOTE_NODE_COUNT(3). 512 * 513 * @param[in] remote_node_table This is the remote node table from which the 514 * remote node allocation is to take place. 515 * @param[in] remote_node_count This is ther remote node count which is one of 516 * SCU_SSP_REMOTE_NODE_COUNT(1) or SCU_STP_REMOTE_NODE_COUNT(3). 517 * 518 * @return U16 This is the remote node index that is returned or an invalid 519 * remote node context. 520 */ 521U16 scic_sds_remote_node_table_allocate_remote_node( 522 SCIC_REMOTE_NODE_TABLE_T * remote_node_table, 523 U32 remote_node_count 524) 525{ 526 U16 remote_node_index = SCIC_SDS_REMOTE_NODE_CONTEXT_INVALID_INDEX; 527 528 if (remote_node_count == SCU_SSP_REMOTE_NODE_COUNT) 529 { 530 remote_node_index = 531 scic_sds_remote_node_table_allocate_single_remote_node( 532 remote_node_table, 0); 533 534 if (remote_node_index == SCIC_SDS_REMOTE_NODE_CONTEXT_INVALID_INDEX) 535 { 536 remote_node_index = 537 scic_sds_remote_node_table_allocate_single_remote_node( 538 remote_node_table, 1); 539 } 540 541 if (remote_node_index == SCIC_SDS_REMOTE_NODE_CONTEXT_INVALID_INDEX) 542 { 543 remote_node_index = 544 scic_sds_remote_node_table_allocate_single_remote_node( 545 remote_node_table, 2); 546 } 547 } 548 else if (remote_node_count == SCU_STP_REMOTE_NODE_COUNT) 549 { 550 remote_node_index = 551 scic_sds_remote_node_table_allocate_triple_remote_node( 552 remote_node_table, 2); 553 } 554 555 return remote_node_index; 556} 557 558/** 559 * This method will free a single remote node index back to the remote node 560 * table. This routine will update the remote node groups 561 * 562 * @param[in] remote_node_table 563 * @param[in] remote_node_index 564 */ 565static 566void scic_sds_remote_node_table_release_single_remote_node( 567 SCIC_REMOTE_NODE_TABLE_T * remote_node_table, 568 U16 remote_node_index 569) 570{ 571 U32 group_index; 572 U8 group_value; 573 574 group_index = remote_node_index / SCU_STP_REMOTE_NODE_COUNT; 575 576 group_value = scic_sds_remote_node_table_get_group_value(remote_node_table, group_index); 577 578 // Assert that we are not trying to add an entry to a slot that is already 579 // full. 580 ASSERT(group_value != SCIC_SDS_REMOTE_NODE_TABLE_FULL_SLOT_VALUE); 581 582 if (group_value == 0x00) 583 { 584 // There are no entries in this slot so it must be added to the single 585 // slot table. 586 scic_sds_remote_node_table_set_group_index(remote_node_table, 0, group_index); 587 } 588 else if ((group_value & (group_value -1)) == 0) 589 { 590 // There is only one entry in this slot so it must be moved from the 591 // single slot table to the dual slot table 592 scic_sds_remote_node_table_clear_group_index(remote_node_table, 0, group_index); 593 scic_sds_remote_node_table_set_group_index(remote_node_table, 1, group_index); 594 } 595 else 596 { 597 // There are two entries in the slot so it must be moved from the dual 598 // slot table to the tripple slot table. 599 scic_sds_remote_node_table_clear_group_index(remote_node_table, 1, group_index); 600 scic_sds_remote_node_table_set_group_index(remote_node_table, 2, group_index); 601 } 602 603 scic_sds_remote_node_table_set_node_index(remote_node_table, remote_node_index); 604} 605 606/** 607 * This method will release a group of three consecutive remote nodes back to 608 * the free remote nodes. 609 * 610 * @param[in] remote_node_table This is the remote node table to which the 611 * remote node index is to be freed. 612 * @param[in] remote_node_index This is the remote node index which is being 613 * freed. 614 */ 615static 616void scic_sds_remote_node_table_release_triple_remote_node( 617 SCIC_REMOTE_NODE_TABLE_T * remote_node_table, 618 U16 remote_node_index 619) 620{ 621 U32 group_index; 622 623 group_index = remote_node_index / SCU_STP_REMOTE_NODE_COUNT; 624 625 scic_sds_remote_node_table_set_group_index( 626 remote_node_table, 2, group_index 627 ); 628 629 scic_sds_remote_node_table_set_group(remote_node_table, group_index); 630} 631 632/** 633 * This method will release the remote node index back into the remote node 634 * table free pool. 635 * 636 * @param[in] remote_node_table The remote node table to which the remote node 637 * index is to be freed. 638 * @param[in] remote_node_count This is the count of consecutive remote nodes 639 * that are to be freed. 640 * @param[in] remote_node_index This is the remote node index of the start of 641 * the number of remote nodes to be freed. 642 */ 643void scic_sds_remote_node_table_release_remote_node_index( 644 SCIC_REMOTE_NODE_TABLE_T * remote_node_table, 645 U32 remote_node_count, 646 U16 remote_node_index 647) 648{ 649 if (remote_node_count == SCU_SSP_REMOTE_NODE_COUNT) 650 { 651 scic_sds_remote_node_table_release_single_remote_node( 652 remote_node_table, remote_node_index); 653 } 654 else if (remote_node_count == SCU_STP_REMOTE_NODE_COUNT) 655 { 656 scic_sds_remote_node_table_release_triple_remote_node( 657 remote_node_table, remote_node_index); 658 } 659} 660 661