URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [trunk/] [linux/] [linux-2.4/] [drivers/] [hotplug/] [acpiphp_res.c] - Blame information for rev 1765

Details | Compare with Previous | View Log


/*
 * ACPI PCI HotPlug Utility functions
 *
 * Copyright (C) 1995,2001 Compaq Computer Corporation
 * Copyright (C) 2001 Greg Kroah-Hartman (greg@kroah.com)
 * Copyright (C) 2001 IBM Corp.
 * Copyright (C) 2002 Hiroshi Aono (h-aono@ap.jp.nec.com)
 * Copyright (C) 2002 Takayoshi Kochi (t-kochi@bq.jp.nec.com)
 * Copyright (C) 2002 NEC Corporation
 *
 * All rights reserved.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or (at
 * your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE, GOOD TITLE or
 * NON INFRINGEMENT.  See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 * Send feedback to <gregkh@us.ibm.com>, <t-kochi@bq.jp.nec.com>
 *
 */
 
#include <linux/config.h>
#include <linux/module.h>
 
#include <linux/kernel.h>
#include <linux/types.h>
#include <linux/proc_fs.h>
#include <linux/sysctl.h>
#include <linux/pci.h>
#include <linux/smp.h>
#include <linux/smp_lock.h>
#include <linux/init.h>
 
#include <linux/string.h>
#include <linux/mm.h>
#include <linux/errno.h>
#include <linux/ioport.h>
#include <linux/slab.h>
#include <linux/interrupt.h>
#include <linux/timer.h>
 
#include <linux/ioctl.h>
#include <linux/fcntl.h>
 
#include <linux/list.h>
 
#include "pci_hotplug.h"
#include "acpiphp.h"
 
#define MY_NAME "acpiphp_res"
 
 
/*
 * sort_by_size - sort nodes by their length, smallest first
 */
static int sort_by_size(struct pci_resource **head)
{
        struct pci_resource *current_res;
        struct pci_resource *next_res;
        int out_of_order = 1;
 
        if (!(*head))
                return 1;
 
        if (!((*head)->next))
                return 0;
 
        while (out_of_order) {
                out_of_order = 0;
 
                /* Special case for swapping list head */
                if (((*head)->next) &&
                    ((*head)->length > (*head)->next->length)) {
                        out_of_order++;
                        current_res = *head;
                        *head = (*head)->next;
                        current_res->next = (*head)->next;
                        (*head)->next = current_res;
                }
 
                current_res = *head;
 
                while (current_res->next && current_res->next->next) {
                        if (current_res->next->length > current_res->next->next->length) {
                                out_of_order++;
                                next_res = current_res->next;
                                current_res->next = current_res->next->next;
                                current_res = current_res->next;
                                next_res->next = current_res->next;
                                current_res->next = next_res;
                        } else
                                current_res = current_res->next;
                }
        }  /* End of out_of_order loop */
 
        return 0;
}
 
 
/*
 * sort_by_max_size - sort nodes by their length, largest first
 */
static int sort_by_max_size(struct pci_resource **head)
{
        struct pci_resource *current_res;
        struct pci_resource *next_res;
        int out_of_order = 1;
 
        if (!(*head))
                return 1;
 
        if (!((*head)->next))
                return 0;
 
        while (out_of_order) {
                out_of_order = 0;
 
                /* Special case for swapping list head */
                if (((*head)->next) &&
                    ((*head)->length < (*head)->next->length)) {
                        out_of_order++;
                        current_res = *head;
                        *head = (*head)->next;
                        current_res->next = (*head)->next;
                        (*head)->next = current_res;
                }
 
                current_res = *head;
 
                while (current_res->next && current_res->next->next) {
                        if (current_res->next->length < current_res->next->next->length) {
                                out_of_order++;
                                next_res = current_res->next;
                                current_res->next = current_res->next->next;
                                current_res = current_res->next;
                                next_res->next = current_res->next;
                                current_res->next = next_res;
                        } else
                                current_res = current_res->next;
                }
        }  /* End of out_of_order loop */
 
        return 0;
}
 
/**
 * get_io_resource - get resource for I/O ports
 *
 * this function sorts the resource list by size and then
 * returns the first node of "size" length that is not in the
 * ISA aliasing window.  If it finds a node larger than "size"
 * it will split it up.
 *
 * size must be a power of two.
 *
 * difference from get_resource is handling of ISA aliasing space.
 *
 */
struct pci_resource *acpiphp_get_io_resource (struct pci_resource **head, u32 size)
{
        struct pci_resource *prevnode;
        struct pci_resource *node;
        struct pci_resource *split_node;
        u64 temp_qword;
 
        if (!(*head))
                return NULL;
 
        if (acpiphp_resource_sort_and_combine(head))
                return NULL;
 
        if (sort_by_size(head))
                return NULL;
 
        for (node = *head; node; node = node->next) {
                if (node->length < size)
                        continue;
 
                if (node->base & (size - 1)) {
                        /* this one isn't base aligned properly
                           so we'll make a new entry and split it up */
                        temp_qword = (node->base | (size-1)) + 1;
 
                        /* Short circuit if adjusted size is too small */
                        if ((node->length - (temp_qword - node->base)) < size)
                                continue;
 
                        split_node = acpiphp_make_resource(node->base, temp_qword - node->base);
 
                        if (!split_node)
                                return NULL;
 
                        node->base = temp_qword;
                        node->length -= split_node->length;
 
                        /* Put it in the list */
                        split_node->next = node->next;
                        node->next = split_node;
                } /* End of non-aligned base */
 
                /* Don't need to check if too small since we already did */
                if (node->length > size) {
                        /* this one is longer than we need
                           so we'll make a new entry and split it up */
                        split_node = acpiphp_make_resource(node->base + size, node->length - size);
 
                        if (!split_node)
                                return NULL;
 
                        node->length = size;
 
                        /* Put it in the list */
                        split_node->next = node->next;
                        node->next = split_node;
                }  /* End of too big on top end */
 
                /* For IO make sure it's not in the ISA aliasing space */
                if (node->base & 0x300L)
                        continue;
 
                /* If we got here, then it is the right size
                   Now take it out of the list */
                if (*head == node) {
                        *head = node->next;
                } else {
                        prevnode = *head;
                        while (prevnode->next != node)
                                prevnode = prevnode->next;
 
                        prevnode->next = node->next;
                }
                node->next = NULL;
                /* Stop looping */
                break;
        }
 
        return node;
}
 
 
/**
 * get_max_resource - get the largest resource
 *
 * Gets the largest node that is at least "size" big from the
 * list pointed to by head.  It aligns the node on top and bottom
 * to "size" alignment before returning it.
 */
struct pci_resource *acpiphp_get_max_resource (struct pci_resource **head, u32 size)
{
        struct pci_resource *max;
        struct pci_resource *temp;
        struct pci_resource *split_node;
        u64 temp_qword;
 
        if (!(*head))
                return NULL;
 
        if (acpiphp_resource_sort_and_combine(head))
                return NULL;
 
        if (sort_by_max_size(head))
                return NULL;
 
        for (max = *head;max; max = max->next) {
 
                /* If not big enough we could probably just bail,
                   instead we'll continue to the next. */
                if (max->length < size)
                        continue;
 
                if (max->base & (size - 1)) {
                        /* this one isn't base aligned properly
                           so we'll make a new entry and split it up */
                        temp_qword = (max->base | (size-1)) + 1;
 
                        /* Short circuit if adjusted size is too small */
                        if ((max->length - (temp_qword - max->base)) < size)
                                continue;
 
                        split_node = acpiphp_make_resource(max->base, temp_qword - max->base);
 
                        if (!split_node)
                                return NULL;
 
                        max->base = temp_qword;
                        max->length -= split_node->length;
 
                        /* Put it next in the list */
                        split_node->next = max->next;
                        max->next = split_node;
                }
 
                if ((max->base + max->length) & (size - 1)) {
                        /* this one isn't end aligned properly at the top
                           so we'll make a new entry and split it up */
                        temp_qword = ((max->base + max->length) & ~(size - 1));
 
                        split_node = acpiphp_make_resource(temp_qword,
                                                           max->length + max->base - temp_qword);
 
                        if (!split_node)
                                return NULL;
 
                        max->length -= split_node->length;
 
                        /* Put it in the list */
                        split_node->next = max->next;
                        max->next = split_node;
                }
 
                /* Make sure it didn't shrink too much when we aligned it */
                if (max->length < size)
                        continue;
 
                /* Now take it out of the list */
                temp = (struct pci_resource*) *head;
                if (temp == max) {
                        *head = max->next;
                } else {
                        while (temp && temp->next != max) {
                                temp = temp->next;
                        }
 
                        temp->next = max->next;
                }
 
                max->next = NULL;
                return max;
        }
 
        /* If we get here, we couldn't find one */
        return NULL;
}
 
 
/**
 * get_resource - get resource (mem, pfmem)
 *
 * this function sorts the resource list by size and then
 * returns the first node of "size" length.  If it finds a node
 * larger than "size" it will split it up.
 *
 * size must be a power of two.
 *
 */
struct pci_resource *acpiphp_get_resource (struct pci_resource **head, u32 size)
{
        struct pci_resource *prevnode;
        struct pci_resource *node;
        struct pci_resource *split_node;
        u64 temp_qword;
 
        if (!(*head))
                return NULL;
 
        if (acpiphp_resource_sort_and_combine(head))
                return NULL;
 
        if (sort_by_size(head))
                return NULL;
 
        for (node = *head; node; node = node->next) {
                dbg("%s: req_size =%x node=%p, base=%x, length=%x\n",
                    __FUNCTION__, size, node, (u32)node->base, node->length);
                if (node->length < size)
                        continue;
 
                if (node->base & (size - 1)) {
                        dbg("%s: not aligned\n", __FUNCTION__);
                        /* this one isn't base aligned properly
                           so we'll make a new entry and split it up */
                        temp_qword = (node->base | (size-1)) + 1;
 
                        /* Short circuit if adjusted size is too small */
                        if ((node->length - (temp_qword - node->base)) < size)
                                continue;
 
                        split_node = acpiphp_make_resource(node->base, temp_qword - node->base);
 
                        if (!split_node)
                                return NULL;
 
                        node->base = temp_qword;
                        node->length -= split_node->length;
 
                        /* Put it in the list */
                        split_node->next = node->next;
                        node->next = split_node;
                } /* End of non-aligned base */
 
                /* Don't need to check if too small since we already did */
                if (node->length > size) {
                        dbg("%s: too big\n", __FUNCTION__);
                        /* this one is longer than we need
                           so we'll make a new entry and split it up */
                        split_node = acpiphp_make_resource(node->base + size, node->length - size);
 
                        if (!split_node)
                                return NULL;
 
                        node->length = size;
 
                        /* Put it in the list */
                        split_node->next = node->next;
                        node->next = split_node;
                }  /* End of too big on top end */
 
                dbg("%s: got one!!!\n", __FUNCTION__);
                /* If we got here, then it is the right size
                   Now take it out of the list */
                if (*head == node) {
                        *head = node->next;
                } else {
                        prevnode = *head;
                        while (prevnode->next != node)
                                prevnode = prevnode->next;
 
                        prevnode->next = node->next;
                }
                node->next = NULL;
                /* Stop looping */
                break;
        }
        return node;
}
 
/**
 * get_resource_with_base - get resource with specific base address
 *
 * this function
 * returns the first node of "size" length located at specified base address.
 * If it finds a node larger than "size" it will split it up.
 *
 * size must be a power of two.
 *
 */
struct pci_resource *acpiphp_get_resource_with_base (struct pci_resource **head, u64 base, u32 size)
{
        struct pci_resource *prevnode;
        struct pci_resource *node;
        struct pci_resource *split_node;
        u64 temp_qword;
 
        if (!(*head))
                return NULL;
 
        if (acpiphp_resource_sort_and_combine(head))
                return NULL;
 
        for (node = *head; node; node = node->next) {
                dbg(": 1st req_base=%x req_size =%x node=%p, base=%x, length=%x\n",
                    (u32)base, size, node, (u32)node->base, node->length);
                if (node->base > base)
                        continue;
 
                if ((node->base + node->length) < (base + size))
                        continue;
 
                if (node->base < base) {
                        dbg(": split 1\n");
                        /* this one isn't base aligned properly
                           so we'll make a new entry and split it up */
                        temp_qword = base;
 
                        /* Short circuit if adjusted size is too small */
                        if ((node->length - (temp_qword - node->base)) < size)
                                continue;
 
                        split_node = acpiphp_make_resource(node->base, temp_qword - node->base);
 
                        if (!split_node)
                                return NULL;
 
                        node->base = temp_qword;
                        node->length -= split_node->length;
 
                        /* Put it in the list */
                        split_node->next = node->next;
                        node->next = split_node;
                }
 
                dbg(": 2nd req_base=%x req_size =%x node=%p, base=%x, length=%x\n",
                    (u32)base, size, node, (u32)node->base, node->length);
 
                /* Don't need to check if too small since we already did */
                if (node->length > size) {
                        dbg(": split 2\n");
                        /* this one is longer than we need
                           so we'll make a new entry and split it up */
                        split_node = acpiphp_make_resource(node->base + size, node->length - size);
 
                        if (!split_node)
                                return NULL;
 
                        node->length = size;
 
                        /* Put it in the list */
                        split_node->next = node->next;
                        node->next = split_node;
                }  /* End of too big on top end */
 
                dbg(": got one!!!\n");
                /* If we got here, then it is the right size
                   Now take it out of the list */
                if (*head == node) {
                        *head = node->next;
                } else {
                        prevnode = *head;
                        while (prevnode->next != node)
                                prevnode = prevnode->next;
 
                        prevnode->next = node->next;
                }
                node->next = NULL;
                /* Stop looping */
                break;
        }
        return node;
}
 
 
/**
 * acpiphp_resource_sort_and_combine
 *
 * Sorts all of the nodes in the list in ascending order by
 * their base addresses.  Also does garbage collection by
 * combining adjacent nodes.
 *
 * returns 0 if success
 */
int acpiphp_resource_sort_and_combine (struct pci_resource **head)
{
        struct pci_resource *node1;
        struct pci_resource *node2;
        int out_of_order = 1;
 
        if (!(*head))
                return 1;
 
        dbg("*head->next = %p\n",(*head)->next);
 
        if (!(*head)->next)
                return 0;        /* only one item on the list, already sorted! */
 
        dbg("*head->base = 0x%x\n",(u32)(*head)->base);
        dbg("*head->next->base = 0x%x\n", (u32)(*head)->next->base);
        while (out_of_order) {
                out_of_order = 0;
 
                /* Special case for swapping list head */
                if (((*head)->next) &&
                    ((*head)->base > (*head)->next->base)) {
                        node1 = *head;
                        (*head) = (*head)->next;
                        node1->next = (*head)->next;
                        (*head)->next = node1;
                        out_of_order++;
                }
 
                node1 = (*head);
 
                while (node1->next && node1->next->next) {
                        if (node1->next->base > node1->next->next->base) {
                                out_of_order++;
                                node2 = node1->next;
                                node1->next = node1->next->next;
                                node1 = node1->next;
                                node2->next = node1->next;
                                node1->next = node2;
                        } else
                                node1 = node1->next;
                }
        }  /* End of out_of_order loop */
 
        node1 = *head;
 
        while (node1 && node1->next) {
                if ((node1->base + node1->length) == node1->next->base) {
                        /* Combine */
                        dbg("8..\n");
                        node1->length += node1->next->length;
                        node2 = node1->next;
                        node1->next = node1->next->next;
                        kfree(node2);
                } else
                        node1 = node1->next;
        }
 
        return 0;
}
 
 
/**
 * acpiphp_make_resource - make resource structure
 * @base: base address of a resource
 * @length: length of a resource
 */
struct pci_resource *acpiphp_make_resource (u64 base, u32 length)
{
        struct pci_resource *res;
 
        res = kmalloc(sizeof(struct pci_resource), GFP_KERNEL);
        if (res) {
                memset(res, 0, sizeof(struct pci_resource));
                res->base = base;
                res->length = length;
        }
 
        return res;
}
 
 
/**
 * acpiphp_move_resource - move linked resources from one to another
 * @from: head of linked resource list
 * @to: head of linked resource list
 */
void acpiphp_move_resource (struct pci_resource **from, struct pci_resource **to)
{
        struct pci_resource *tmp;
 
        while (*from) {
                tmp = (*from)->next;
                (*from)->next = *to;
                *to = *from;
                *from = tmp;
        }
 
        /* *from = NULL is guaranteed */
}
 
 
/**
 * acpiphp_free_resource - free all linked resources
 * @res: head of linked resource list
 */
void acpiphp_free_resource (struct pci_resource **res)
{
        struct pci_resource *tmp;
 
        while (*res) {
                tmp = (*res)->next;
                kfree(*res);
                *res = tmp;
        }
 
        /* *res = NULL is guaranteed */
}
 
 
/* debug support functions;  will go away sometime :) */
static void dump_resource(struct pci_resource *head)
{
        struct pci_resource *p;
        int cnt;
 
        p = head;
        cnt = 0;
 
        while (p) {
                dbg("[%02d] %08x - %08x\n",
                    cnt++, (u32)p->base, (u32)p->base + p->length - 1);
                p = p->next;
        }
}
 
void acpiphp_dump_resource(struct acpiphp_bridge *bridge)
{
        dbg("I/O resource:\n");
        dump_resource(bridge->io_head);
        dbg("MEM resource:\n");
        dump_resource(bridge->mem_head);
        dbg("PMEM resource:\n");
        dump_resource(bridge->p_mem_head);
        dbg("BUS resource:\n");
        dump_resource(bridge->bus_head);
}
 
void acpiphp_dump_func_resource(struct acpiphp_func *func)
{
        dbg("I/O resource:\n");
        dump_resource(func->io_head);
        dbg("MEM resource:\n");
        dump_resource(func->mem_head);
        dbg("PMEM resource:\n");
        dump_resource(func->p_mem_head);
        dbg("BUS resource:\n");
        dump_resource(func->bus_head);
}

Browse

Tools

Subversion Repositories or1k

[/] [or1k/] [trunk/] [linux/] [linux-2.4/] [drivers/] [hotplug/] [acpiphp_res.c] - Blame information for rev 1765

Line No.	Rev	Author	Line
1	1275	phoenix	`/*`
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/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			`}`