drivers/pci/hotplug/acpiphp_res.c

   1 /*
   2  * ACPI PCI HotPlug Utility functions
   3  *
   4  * Copyright (C) 1995,2001 Compaq Computer Corporation
   5  * Copyright (C) 2001 Greg Kroah-Hartman (greg@kroah.com)
   6  * Copyright (C) 2001 IBM Corp.
   7  * Copyright (C) 2002 Hiroshi Aono (h-aono@ap.jp.nec.com)
   8  * Copyright (C) 2002 Takayoshi Kochi (t-kochi@bq.jp.nec.com)
   9  * Copyright (C) 2002 NEC Corporation
  10  *
  11  * All rights reserved.
  12  *
  13  * This program is free software; you can redistribute it and/or modify
  14  * it under the terms of the GNU General Public License as published by
  15  * the Free Software Foundation; either version 2 of the License, or (at
  16  * your option) any later version.
  17  *
  18  * This program is distributed in the hope that it will be useful, but
  19  * WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE, GOOD TITLE or
  21  * NON INFRINGEMENT.  See the GNU General Public License for more
  22  * details.
  23  *
  24  * You should have received a copy of the GNU General Public License
  25  * along with this program; if not, write to the Free Software
  26  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  27  *
  28  * Send feedback to <gregkh@us.ibm.com>, <t-kochi@bq.jp.nec.com>
  29  *
  30  */
  31
  32 #include <linux/init.h>
  33 #include <linux/module.h>
  34
  35 #include <linux/kernel.h>
  36 #include <linux/types.h>
  37 #include <linux/proc_fs.h>
  38 #include <linux/sysctl.h>
  39 #include <linux/pci.h>
  40 #include <linux/smp.h>
  41 #include <linux/smp_lock.h>
  42
  43 #include <linux/string.h>
  44 #include <linux/mm.h>
  45 #include <linux/errno.h>
  46 #include <linux/ioport.h>
  47 #include <linux/slab.h>
  48 #include <linux/interrupt.h>
  49 #include <linux/timer.h>
  50
  51 #include <linux/ioctl.h>
  52 #include <linux/fcntl.h>
  53
  54 #include <linux/list.h>
  55
  56 #include "pci_hotplug.h"
  57 #include "acpiphp.h"
  58
  59 #define MY_NAME "acpiphp_res"
  60
  61
  62 /*
  63  * sort_by_size - sort nodes by their length, smallest first
  64  */
  65 static int sort_by_size(struct pci_resource **head)
  66 {
  67         struct pci_resource *current_res;
  68         struct pci_resource *next_res;
  69         int out_of_order = 1;
  70
  71         if (!(*head))
  72                 return 1;
  73
  74         if (!((*head)->next))
  75                 return 0;
  76
  77         while (out_of_order) {
  78                 out_of_order = 0;
  79
  80                 /* Special case for swapping list head */
  81                 if (((*head)->next) &&
  82                     ((*head)->length > (*head)->next->length)) {
  83                         out_of_order++;
  84                         current_res = *head;
  85                         *head = (*head)->next;
  86                         current_res->next = (*head)->next;
  87                         (*head)->next = current_res;
  88                 }
  89
  90                 current_res = *head;
  91
  92                 while (current_res->next && current_res->next->next) {
  93                         if (current_res->next->length > current_res->next->next->length) {
  94                                 out_of_order++;
  95                                 next_res = current_res->next;
  96                                 current_res->next = current_res->next->next;
  97                                 current_res = current_res->next;
  98                                 next_res->next = current_res->next;
  99                                 current_res->next = next_res;
 100                         } else
 101                                 current_res = current_res->next;
 102                 }
 103         }  /* End of out_of_order loop */
 104
 105         return 0;
 106 }
 107
 108
 109 /*
 110  * sort_by_max_size - sort nodes by their length, largest first
 111  */
 112 static int sort_by_max_size(struct pci_resource **head)
 113 {
 114         struct pci_resource *current_res;
 115         struct pci_resource *next_res;
 116         int out_of_order = 1;
 117
 118         if (!(*head))
 119                 return 1;
 120
 121         if (!((*head)->next))
 122                 return 0;
 123
 124         while (out_of_order) {
 125                 out_of_order = 0;
 126
 127                 /* Special case for swapping list head */
 128                 if (((*head)->next) &&
 129                     ((*head)->length < (*head)->next->length)) {
 130                         out_of_order++;
 131                         current_res = *head;
 132                         *head = (*head)->next;
 133                         current_res->next = (*head)->next;
 134                         (*head)->next = current_res;
 135                 }
 136
 137                 current_res = *head;
 138
 139                 while (current_res->next && current_res->next->next) {
 140                         if (current_res->next->length < current_res->next->next->length) {
 141                                 out_of_order++;
 142                                 next_res = current_res->next;
 143                                 current_res->next = current_res->next->next;
 144                                 current_res = current_res->next;
 145                                 next_res->next = current_res->next;
 146                                 current_res->next = next_res;
 147                         } else
 148                                 current_res = current_res->next;
 149                 }
 150         }  /* End of out_of_order loop */
 151
 152         return 0;
 153 }
 154
 155 /**
 156  * get_io_resource - get resource for I/O ports
 157  *
 158  * this function sorts the resource list by size and then
 159  * returns the first node of "size" length that is not in the
 160  * ISA aliasing window.  If it finds a node larger than "size"
 161  * it will split it up.
 162  *
 163  * size must be a power of two.
 164  *
 165  * difference from get_resource is handling of ISA aliasing space.
 166  *
 167  */
 168 struct pci_resource *acpiphp_get_io_resource (struct pci_resource **head, u32 size)
 169 {
 170         struct pci_resource *prevnode;
 171         struct pci_resource *node;
 172         struct pci_resource *split_node;
 173         u64 temp_qword;
 174
 175         if (!(*head))
 176                 return NULL;
 177
 178         if (acpiphp_resource_sort_and_combine(head))
 179                 return NULL;
 180
 181         if (sort_by_size(head))
 182                 return NULL;
 183
 184         for (node = *head; node; node = node->next) {
 185                 if (node->length < size)
 186                         continue;
 187
 188                 if (node->base & (size - 1)) {
 189                         /* this one isn't base aligned properly
 190                            so we'll make a new entry and split it up */
 191                         temp_qword = (node->base | (size-1)) + 1;
 192
 193                         /* Short circuit if adjusted size is too small */
 194                         if ((node->length - (temp_qword - node->base)) < size)
 195                                 continue;
 196
 197                         split_node = acpiphp_make_resource(node->base, temp_qword - node->base);
 198
 199                         if (!split_node)
 200                                 return NULL;
 201
 202                         node->base = temp_qword;
 203                         node->length -= split_node->length;
 204
 205                         /* Put it in the list */
 206                         split_node->next = node->next;
 207                         node->next = split_node;
 208                 } /* End of non-aligned base */
 209
 210                 /* Don't need to check if too small since we already did */
 211                 if (node->length > size) {
 212                         /* this one is longer than we need
 213                            so we'll make a new entry and split it up */
 214                         split_node = acpiphp_make_resource(node->base + size, node->length - size);
 215
 216                         if (!split_node)
 217                                 return NULL;
 218
 219                         node->length = size;
 220
 221                         /* Put it in the list */
 222                         split_node->next = node->next;
 223                         node->next = split_node;
 224                 }  /* End of too big on top end */
 225
 226                 /* For IO make sure it's not in the ISA aliasing space */
 227                 if ((node->base & 0x300L) && !(node->base & 0xfffff000))
 228                         continue;
 229
 230                 /* If we got here, then it is the right size
 231                    Now take it out of the list */
 232                 if (*head == node) {
 233                         *head = node->next;
 234                 } else {
 235                         prevnode = *head;
 236                         while (prevnode->next != node)
 237                                 prevnode = prevnode->next;
 238
 239                         prevnode->next = node->next;
 240                 }
 241                 node->next = NULL;
 242                 /* Stop looping */
 243                 break;
 244         }
 245
 246         return node;
 247 }
 248
 249
 250 /**
 251  * get_max_resource - get the largest resource
 252  *
 253  * Gets the largest node that is at least "size" big from the
 254  * list pointed to by head.  It aligns the node on top and bottom
 255  * to "size" alignment before returning it.
 256  */
 257 struct pci_resource *acpiphp_get_max_resource (struct pci_resource **head, u32 size)
 258 {
 259         struct pci_resource *max;
 260         struct pci_resource *temp;
 261         struct pci_resource *split_node;
 262         u64 temp_qword;
 263
 264         if (!(*head))
 265                 return NULL;
 266
 267         if (acpiphp_resource_sort_and_combine(head))
 268                 return NULL;
 269
 270         if (sort_by_max_size(head))
 271                 return NULL;
 272
 273         for (max = *head;max; max = max->next) {
 274
 275                 /* If not big enough we could probably just bail,
 276                    instead we'll continue to the next. */
 277                 if (max->length < size)
 278                         continue;
 279
 280                 if (max->base & (size - 1)) {
 281                         /* this one isn't base aligned properly
 282                            so we'll make a new entry and split it up */
 283                         temp_qword = (max->base | (size-1)) + 1;
 284
 285                         /* Short circuit if adjusted size is too small */
 286                         if ((max->length - (temp_qword - max->base)) < size)
 287                                 continue;
 288
 289                         split_node = acpiphp_make_resource(max->base, temp_qword - max->base);
 290
 291                         if (!split_node)
 292                                 return NULL;
 293
 294                         max->base = temp_qword;
 295                         max->length -= split_node->length;
 296
 297                         /* Put it next in the list */
 298                         split_node->next = max->next;
 299                         max->next = split_node;
 300                 }
 301
 302                 if ((max->base + max->length) & (size - 1)) {
 303                         /* this one isn't end aligned properly at the top
 304                            so we'll make a new entry and split it up */
 305                         temp_qword = ((max->base + max->length) & ~(size - 1));
 306
 307                         split_node = acpiphp_make_resource(temp_qword,
 308                                                            max->length + max->base - temp_qword);
 309
 310                         if (!split_node)
 311                                 return NULL;
 312
 313                         max->length -= split_node->length;
 314
 315                         /* Put it in the list */
 316                         split_node->next = max->next;
 317                         max->next = split_node;
 318                 }
 319
 320                 /* Make sure it didn't shrink too much when we aligned it */
 321                 if (max->length < size)
 322                         continue;
 323
 324                 /* Now take it out of the list */
 325                 temp = (struct pci_resource*) *head;
 326                 if (temp == max) {
 327                         *head = max->next;
 328                 } else {
 329                         while (temp && temp->next != max) {
 330                                 temp = temp->next;
 331                         }
 332
 333                         temp->next = max->next;
 334                 }
 335
 336                 max->next = NULL;
 337                 return max;
 338         }
 339
 340         /* If we get here, we couldn't find one */
 341         return NULL;
 342 }
 343
 344
 345 /**
 346  * get_resource - get resource (mem, pfmem)
 347  *
 348  * this function sorts the resource list by size and then
 349  * returns the first node of "size" length.  If it finds a node
 350  * larger than "size" it will split it up.
 351  *
 352  * size must be a power of two.
 353  *
 354  */
 355 struct pci_resource *acpiphp_get_resource (struct pci_resource **head, u32 size)
 356 {
 357         struct pci_resource *prevnode;
 358         struct pci_resource *node;
 359         struct pci_resource *split_node;
 360         u64 temp_qword;
 361
 362         if (!(*head))
 363                 return NULL;
 364
 365         if (acpiphp_resource_sort_and_combine(head))
 366                 return NULL;
 367
 368         if (sort_by_size(head))
 369                 return NULL;
 370
 371         for (node = *head; node; node = node->next) {
 372                 dbg("%s: req_size =%x node=%p, base=%x, length=%x\n",
 373                     __FUNCTION__, size, node, (u32)node->base, node->length);
 374                 if (node->length < size)
 375                         continue;
 376
 377                 if (node->base & (size - 1)) {
 378                         dbg("%s: not aligned\n", __FUNCTION__);
 379                         /* this one isn't base aligned properly
 380                            so we'll make a new entry and split it up */
 381                         temp_qword = (node->base | (size-1)) + 1;
 382
 383                         /* Short circuit if adjusted size is too small */
 384                         if ((node->length - (temp_qword - node->base)) < size)
 385                                 continue;
 386
 387                         split_node = acpiphp_make_resource(node->base, temp_qword - node->base);
 388
 389                         if (!split_node)
 390                                 return NULL;
 391
 392                         node->base = temp_qword;
 393                         node->length -= split_node->length;
 394
 395                         /* Put it in the list */
 396                         split_node->next = node->next;
 397                         node->next = split_node;
 398                 } /* End of non-aligned base */
 399
 400                 /* Don't need to check if too small since we already did */
 401                 if (node->length > size) {
 402                         dbg("%s: too big\n", __FUNCTION__);
 403                         /* this one is longer than we need
 404                            so we'll make a new entry and split it up */
 405                         split_node = acpiphp_make_resource(node->base + size, node->length - size);
 406
 407                         if (!split_node)
 408                                 return NULL;
 409
 410                         node->length = size;
 411
 412                         /* Put it in the list */
 413                         split_node->next = node->next;
 414                         node->next = split_node;
 415                 }  /* End of too big on top end */
 416
 417                 dbg("%s: got one!!!\n", __FUNCTION__);
 418                 /* If we got here, then it is the right size
 419                    Now take it out of the list */
 420                 if (*head == node) {
 421                         *head = node->next;
 422                 } else {
 423                         prevnode = *head;
 424                         while (prevnode->next != node)
 425                                 prevnode = prevnode->next;
 426
 427                         prevnode->next = node->next;
 428                 }
 429                 node->next = NULL;
 430                 /* Stop looping */
 431                 break;
 432         }
 433         return node;
 434 }
 435
 436 /**
 437  * get_resource_with_base - get resource with specific base address
 438  *
 439  * this function
 440  * returns the first node of "size" length located at specified base address.
 441  * If it finds a node larger than "size" it will split it up.
 442  *
 443  * size must be a power of two.
 444  *
 445  */
 446 struct pci_resource *acpiphp_get_resource_with_base (struct pci_resource **head, u64 base, u32 size)
 447 {
 448         struct pci_resource *prevnode;
 449         struct pci_resource *node;
 450         struct pci_resource *split_node;
 451         u64 temp_qword;
 452
 453         if (!(*head))
 454                 return NULL;
 455
 456         if (acpiphp_resource_sort_and_combine(head))
 457                 return NULL;
 458
 459         for (node = *head; node; node = node->next) {
 460                 dbg(": 1st req_base=%x req_size =%x node=%p, base=%x, length=%x\n",
 461                     (u32)base, size, node, (u32)node->base, node->length);
 462                 if (node->base > base)
 463                         continue;
 464
 465                 if ((node->base + node->length) < (base + size))
 466                         continue;
 467
 468                 if (node->base < base) {
 469                         dbg(": split 1\n");
 470                         /* this one isn't base aligned properly
 471                            so we'll make a new entry and split it up */
 472                         temp_qword = base;
 473
 474                         /* Short circuit if adjusted size is too small */
 475                         if ((node->length - (temp_qword - node->base)) < size)
 476                                 continue;
 477
 478                         split_node = acpiphp_make_resource(node->base, temp_qword - node->base);
 479
 480                         if (!split_node)
 481                                 return NULL;
 482
 483                         node->base = temp_qword;
 484                         node->length -= split_node->length;
 485
 486                         /* Put it in the list */
 487                         split_node->next = node->next;
 488                         node->next = split_node;
 489                 }
 490
 491                 dbg(": 2nd req_base=%x req_size =%x node=%p, base=%x, length=%x\n",
 492                     (u32)base, size, node, (u32)node->base, node->length);
 493
 494                 /* Don't need to check if too small since we already did */
 495                 if (node->length > size) {
 496                         dbg(": split 2\n");
 497                         /* this one is longer than we need
 498                            so we'll make a new entry and split it up */
 499                         split_node = acpiphp_make_resource(node->base + size, node->length - size);
 500
 501                         if (!split_node)
 502                                 return NULL;
 503
 504                         node->length = size;
 505
 506                         /* Put it in the list */
 507                         split_node->next = node->next;
 508                         node->next = split_node;
 509                 }  /* End of too big on top end */
 510
 511                 dbg(": got one!!!\n");
 512                 /* If we got here, then it is the right size
 513                    Now take it out of the list */
 514                 if (*head == node) {
 515                         *head = node->next;
 516                 } else {
 517                         prevnode = *head;
 518                         while (prevnode->next != node)
 519                                 prevnode = prevnode->next;
 520
 521                         prevnode->next = node->next;
 522                 }
 523                 node->next = NULL;
 524                 /* Stop looping */
 525                 break;
 526         }
 527         return node;
 528 }
 529
 530
 531 /**
 532  * acpiphp_resource_sort_and_combine
 533  *
 534  * Sorts all of the nodes in the list in ascending order by
 535  * their base addresses.  Also does garbage collection by
 536  * combining adjacent nodes.
 537  *
 538  * returns 0 if success
 539  */
 540 int acpiphp_resource_sort_and_combine (struct pci_resource **head)
 541 {
 542         struct pci_resource *node1;
 543         struct pci_resource *node2;
 544         int out_of_order = 1;
 545
 546         if (!(*head))
 547                 return 1;
 548
 549         dbg("*head->next = %p\n",(*head)->next);
 550
 551         if (!(*head)->next)
 552                 return 0;       /* only one item on the list, already sorted! */
 553
 554         dbg("*head->base = 0x%x\n",(u32)(*head)->base);
 555         dbg("*head->next->base = 0x%x\n", (u32)(*head)->next->base);
 556         while (out_of_order) {
 557                 out_of_order = 0;
 558
 559                 /* Special case for swapping list head */
 560                 if (((*head)->next) &&
 561                     ((*head)->base > (*head)->next->base)) {
 562                         node1 = *head;
 563                         (*head) = (*head)->next;
 564                         node1->next = (*head)->next;
 565                         (*head)->next = node1;
 566                         out_of_order++;
 567                 }
 568
 569                 node1 = (*head);
 570
 571                 while (node1->next && node1->next->next) {
 572                         if (node1->next->base > node1->next->next->base) {
 573                                 out_of_order++;
 574                                 node2 = node1->next;
 575                                 node1->next = node1->next->next;
 576                                 node1 = node1->next;
 577                                 node2->next = node1->next;
 578                                 node1->next = node2;
 579                         } else
 580                                 node1 = node1->next;
 581                 }
 582         }  /* End of out_of_order loop */
 583
 584         node1 = *head;
 585
 586         while (node1 && node1->next) {
 587                 if ((node1->base + node1->length) == node1->next->base) {
 588                         /* Combine */
 589                         dbg("8..\n");
 590                         node1->length += node1->next->length;
 591                         node2 = node1->next;
 592                         node1->next = node1->next->next;
 593                         kfree(node2);
 594                 } else
 595                         node1 = node1->next;
 596         }
 597
 598         return 0;
 599 }
 600
 601
 602 /**
 603  * acpiphp_make_resource - make resource structure
 604  * @base: base address of a resource
 605  * @length: length of a resource
 606  */
 607 struct pci_resource *acpiphp_make_resource (u64 base, u32 length)
 608 {
 609         struct pci_resource *res;
 610
 611         res = kmalloc(sizeof(struct pci_resource), GFP_KERNEL);
 612         if (res) {
 613                 memset(res, 0, sizeof(struct pci_resource));
 614                 res->base = base;
 615                 res->length = length;
 616         }
 617
 618         return res;
 619 }
 620
 621
 622 /**
 623  * acpiphp_move_resource - move linked resources from one to another
 624  * @from: head of linked resource list
 625  * @to: head of linked resource list
 626  */
 627 void acpiphp_move_resource (struct pci_resource **from, struct pci_resource **to)
 628 {
 629         struct pci_resource *tmp;
 630
 631         while (*from) {
 632                 tmp = (*from)->next;
 633                 (*from)->next = *to;
 634                 *to = *from;
 635                 *from = tmp;
 636         }
 637
 638         /* *from = NULL is guaranteed */
 639 }
 640
 641
 642 /**
 643  * acpiphp_free_resource - free all linked resources
 644  * @res: head of linked resource list
 645  */
 646 void acpiphp_free_resource (struct pci_resource **res)
 647 {
 648         struct pci_resource *tmp;
 649
 650         while (*res) {
 651                 tmp = (*res)->next;
 652                 kfree(*res);
 653                 *res = tmp;
 654         }
 655
 656         /* *res = NULL is guaranteed */
 657 }
 658
 659
 660 /* debug support functions;  will go away sometime :) */
 661 static void dump_resource(struct pci_resource *head)
 662 {
 663         struct pci_resource *p;
 664         int cnt;
 665
 666         p = head;
 667         cnt = 0;
 668
 669         while (p) {
 670                 dbg("[%02d] %08x - %08x\n",
 671                     cnt++, (u32)p->base, (u32)p->base + p->length - 1);
 672                 p = p->next;
 673         }
 674 }
 675
 676 void acpiphp_dump_resource(struct acpiphp_bridge *bridge)
 677 {
 678         dbg("I/O resource:\n");
 679         dump_resource(bridge->io_head);
 680         dbg("MEM resource:\n");
 681         dump_resource(bridge->mem_head);
 682         dbg("PMEM resource:\n");
 683         dump_resource(bridge->p_mem_head);
 684         dbg("BUS resource:\n");
 685         dump_resource(bridge->bus_head);
 686 }
 687
 688 void acpiphp_dump_func_resource(struct acpiphp_func *func)
 689 {
 690         dbg("I/O resource:\n");
 691         dump_resource(func->io_head);
 692         dbg("MEM resource:\n");
 693         dump_resource(func->mem_head);
 694         dbg("PMEM resource:\n");
 695         dump_resource(func->p_mem_head);
 696         dbg("BUS resource:\n");
 697         dump_resource(func->bus_head);
 698 }