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 */
sort_by_size(struct pci_resource ** head)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 */
sort_by_max_size(struct pci_resource ** head)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 */
acpiphp_get_io_resource(struct pci_resource ** head,u32 size)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 */
acpiphp_get_max_resource(struct pci_resource ** head,u32 size)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 */
acpiphp_get_resource(struct pci_resource ** head,u32 size)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 */
acpiphp_get_resource_with_base(struct pci_resource ** head,u64 base,u32 size)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 */
acpiphp_resource_sort_and_combine(struct pci_resource ** head)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 */
acpiphp_make_resource(u64 base,u32 length)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 */
acpiphp_move_resource(struct pci_resource ** from,struct pci_resource ** to)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 */
acpiphp_free_resource(struct pci_resource ** res)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 :) */
dump_resource(struct pci_resource * head)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
acpiphp_dump_resource(struct acpiphp_bridge * bridge)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
acpiphp_dump_func_resource(struct acpiphp_func * func)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 }
699