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