#ifdef KERNEL
#include <IOKit/pci/IOPCIPrivate.h>
#include <IOKit/pci/IOPCIConfigurator.h>
#else
#include <assert.h>
#include <CoreFoundation/CoreFoundation.h>
#include <IOKit/IOKitLib.h>
#include <IOKit/IOKitKeys.h>
#include "IOKit/pci/IOPCIConfigurator.h"
#define panic(x) printf(x)
#endif
IOPCIScalar IOPCIScalarAlign(IOPCIScalar num, IOPCIScalar alignment)
{
return (num + (alignment - 1) & ~(alignment - 1));
}
IOPCIScalar IOPCIScalarTrunc(IOPCIScalar num, IOPCIScalar alignment)
{
return (num & ~(alignment - 1));
}
IOPCIRange * IOPCIRangeAlloc(void)
{
#ifdef KERNEL
return (IONew(IOPCIRange, 1));
#else
return ((IOPCIRange *) malloc(sizeof(IOPCIRange)));
#endif
}
void IOPCIRangeFree(IOPCIRange * range)
{
#ifdef KERNEL
IODelete(range, IOPCIRange, 1);
#else
free(range);
#endif
}
void IOPCIRangeInit(IOPCIRange * range, uint32_t type,
IOPCIScalar start, IOPCIScalar size, IOPCIScalar alignment)
{
bzero(range, sizeof(*range));
range->type = type;
range->start = start;
range->size = 0;
range->proposedSize = size;
range->end = start + size;
range->zero = 0;
range->alignment = alignment ? alignment : size;
range->minAddress = 0;
range->maxAddress = 0xFFFFFFFF;
range->allocations = (IOPCIRange *) &range->end;
}
bool IOPCIRangeListAddRange(IOPCIRange ** rangeList,
uint32_t type,
IOPCIScalar start,
IOPCIScalar size,
IOPCIScalar alignment)
{
IOPCIRange * range;
IOPCIRange * nextRange;
IOPCIRange ** prev;
IOPCIScalar end;
bool result = true;
bool alloc = true;
end = start + size;
for (prev = rangeList; (range = *prev); prev = &range->next)
{
if (((start >= range->start) && (start < range->end))
|| ((end > range->start) && (end <= range->end))
|| ((start < range->start) && (end > range->end)))
{
range = NULL;
result = false;
break;
}
if (end == range->start)
{
range->start = start;
range->size = range->end - range->start;
range->proposedSize = range->size;
alloc = false;
break;
}
if (start == range->end)
{
if ((nextRange = range->next) && (nextRange->start == end))
{
if (nextRange->allocations != (IOPCIRange *) &nextRange->end)
assert(false);
end = nextRange->end;
range->next = nextRange->next;
IOPCIRangeFree(nextRange);
}
range->end = end;
range->size = end - range->start;
range->proposedSize = range->size;
alloc = false;
break;
}
if (range->start > end)
{
alloc = true;
break;
}
}
if (result && alloc)
{
nextRange = IOPCIRangeAlloc();
IOPCIRangeInit(nextRange, type, start, size, alignment);
nextRange->size = nextRange->proposedSize;
nextRange->next = range;
*prev = nextRange;
}
return (result);
}
IOPCIScalar IOPCIRangeListCollapse(IOPCIRange * headRange, IOPCIScalar alignment)
{
IOPCIScalar total = 0;
while (headRange)
{
total += IOPCIRangeCollapse(headRange, alignment);
headRange = headRange->next;
}
return (total);
}
IOPCIScalar IOPCIRangeCollapse(IOPCIRange * headRange, IOPCIScalar alignment)
{
IOPCIScalar start, end, saving;
IOPCIRange * range;
start = 0;
end = 0;
range = headRange->allocations;
do
{
if (!range->size)
break;
if (!start)
start = range->start;
end = range->end;
range = range->nextSubRange;
}
while(true);
start = IOPCIScalarTrunc(start, alignment);
end = IOPCIScalarAlign(end, alignment);
if (start)
headRange->start = start;
headRange->proposedSize = end - start;
saving = headRange->size - headRange->proposedSize;
return (saving);
}
IOPCIScalar IOPCIRangeListLastFree(IOPCIRange * headRange, IOPCIScalar align)
{
IOPCIRange * next;
next = headRange;
while (next)
{
headRange = next;
next = next->next;
}
return (IOPCIRangeLastFree(headRange, align));
}
IOPCIScalar IOPCIRangeLastFree(IOPCIRange * headRange, IOPCIScalar align)
{
IOPCIScalar last;
IOPCIRange * range;
range = headRange->allocations;
last = headRange->start;
do
{
if (!range->size)
break;
last = range->end;
range = range->nextSubRange;
}
while(true);
last = IOPCIScalarAlign(last, align);
if (headRange->end > last)
last = headRange->end - last;
else
last = 0;
return (last);
}
bool IOPCIRangeListAllocateSubRange(IOPCIRange * headRange,
IOPCIRange * newRange,
IOPCIScalar newStart)
{
IOPCIScalar size, len, bestFit = 0;
IOPCIScalar pos, end, endPos, preferAddress = 0;
IOPCIRange * range = NULL;
IOPCIRange * relocateHead = NULL;
IOPCIRange * relocateLast = NULL;
IOPCIRange ** prev;
IOPCIRange ** where = NULL;
IOPCIRange * whereNext = NULL;
size = newRange->proposedSize;
if (!newStart)
newStart = newRange->start;
if (!size) panic("!size");
if ((!newStart) && (newRange->maxAddress >= (1ULL << 32)))
preferAddress = (1ULL << 32);
for (; headRange; headRange = headRange->next)
{
bool splay;
IOPCIScalar rangeStart, rangeEnd;
if (!headRange->size)
continue;
rangeStart = headRange->start;
rangeEnd = headRange->end;
if ((kIOPCIRangeFlagForceReloc & headRange->flags)
&& !(kIOPCIRangeFlagRelocHalf & newRange->flags))
{
if (kIOPCIRangeFlagRelocHalf & headRange->flags) rangeStart += (headRange->size >> 1);
else rangeEnd -= (headRange->size >> 1);
}
pos = newStart;
if (pos)
{
end = newStart + newRange->proposedSize;
if ((pos < rangeStart) || (end > rangeEnd))
continue;
}
else
{
pos = rangeStart;
pos = IOPCIScalarAlign(pos, newRange->alignment);
end = 0;
}
prev = &headRange->allocations;
range = *prev;
splay = false;
do
{
if (range == newRange)
{
range = range->nextSubRange;
continue;
}
if (end)
{
len = range->start + range->size;
if (((pos >= range->start) && (pos < len))
|| ((end > range->start) && (end <= len))
|| ((pos < range->start) && (end > len)))
{
if (false && (kIOPCIRangeFlagRelocatable & range->flags))
{
if (!relocateHead)
relocateHead = relocateLast = range;
else
relocateLast = range;
range = range->nextSubRange;
continue;
}
else
{
range = NULL;
break;
}
}
}
endPos = range->start;
if (kIOPCIRangeFlagMaximizeSize & newRange->flags)
endPos = IOPCIScalarTrunc(endPos, newRange->alignment);
if (pos < rangeStart) pos = rangeStart;
if ((pos >= newRange->minAddress)
&& ((pos + size - 1) <= newRange->maxAddress)
&& (endPos > pos))
{
bool useit;
bool done = (0 != end);
len = endPos - pos;
if ((kIOPCIRangeFlagMaximizeSize & newRange->flags) && headRange->count)
{
IOPCIScalar max;
max = (headRange->size * headRange->pri) / headRange->count;
if (max < newRange->proposedSize) max = newRange->proposedSize;
if (len > max) len = IOPCIScalarTrunc(max, newRange->alignment);
}
useit = (len >= size);
if (useit)
{
if (kIOPCIRangeFlagMaximizeSize & newRange->flags)
{
size = len;
}
else if (!done)
{
if (splay)
{
useit = (len > bestFit) || (preferAddress && (pos >= preferAddress));
if (useit)
{
IOPCIScalar bump;
bump = IOPCIScalarTrunc(len >> 1, newRange->alignment);
if (bump < (len - size))
pos += bump;
}
}
else if (!(kIOPCIRangeFlagSplay & newRange->flags))
{
len -= size; useit = ((len < bestFit) || !bestFit || (preferAddress && (pos >= preferAddress)));
done = (useit && (0 == len));
}
}
}
if (useit)
{
bestFit = len;
where = prev;
whereNext = range;
newRange->start = pos;
newRange->end = pos + size;
if (preferAddress && (pos >= preferAddress))
preferAddress = 0;
if (done && !preferAddress)
{
break;
}
}
}
if (!range->size)
{
range = NULL;
break;
}
if (!end)
{
pos = IOPCIScalarAlign(range->start + range->size, newRange->alignment);
}
splay = (kIOPCIRangeFlagSplay & range->flags);
prev = &range->nextSubRange;
range = *prev;
}
while(true);
}
if (where)
{
if (relocateHead)
{
IOPCIRange * next = relocateHead;
do
{
relocateHead = next;
next = relocateHead->nextSubRange;
relocateHead->nextSubRange = NULL;
do
{
range = relocateHead->allocations;
if (!range->size)
break;
IOPCIRangeListDeallocateSubRange(relocateHead, range);
}
while(true);
relocateHead->size = 0;
relocateHead->start = 0;
}
while (relocateHead != relocateLast);
whereNext = next;
}
newRange->size = size;
newRange->proposedSize = size;
newRange->nextSubRange = whereNext;
*where = newRange;
}
return (where != NULL);
}
bool IOPCIRangeListDeallocateSubRange(IOPCIRange * headRange,
IOPCIRange * oldRange)
{
IOPCIRange * range = NULL;
IOPCIRange ** prev = NULL;
do
{
range = oldRange->allocations;
if (!range->size)
break;
IOPCIRangeListDeallocateSubRange(oldRange, range);
}
while(true);
for (range = NULL;
headRange && !range;
headRange = headRange->next)
{
prev = &headRange->allocations;
do
{
range = *prev;
if (range == oldRange)
break;
if (!range->size)
{
range = NULL;
break;
}
}
while (prev = &range->nextSubRange, true);
}
if (range)
{
*prev = range->nextSubRange;
oldRange->nextSubRange = NULL;
oldRange->size = 0;
}
return (range != 0);
}
bool IOPCIRangeAppendSubRange(IOPCIRange ** list,
IOPCIRange * newRange )
{
bool result = false;
IOPCIRange ** prev;
IOPCIRange * range;
prev = list;
do
{
range = *prev;
if (!range)
break;
if (range->start && ((range->start < newRange->start) || !newRange->start))
continue;
if (newRange->start && !range->start)
break;
if (((kIOPCIRangeFlagSplay | kIOPCIRangeFlagMaximizeSize) & newRange->flags)
&& !((kIOPCIRangeFlagSplay | kIOPCIRangeFlagMaximizeSize) & range->flags))
continue;
if (((kIOPCIRangeFlagSplay | kIOPCIRangeFlagMaximizeSize) & range->flags)
&& !((kIOPCIRangeFlagSplay | kIOPCIRangeFlagMaximizeSize) & newRange->flags))
break;
if (newRange->alignment > range->alignment)
break;
if (newRange->proposedSize > range->proposedSize)
break;
}
while (prev = &range->nextSubRange, true);
*prev = newRange;
newRange->nextSubRange = range;
result = true;
return (result);
}
#ifndef KERNEL
#define kprintf(fmt, args...) printf(fmt, ## args)
#endif
void IOPCIRangeDump(IOPCIRange * head)
{
IOPCIRange * range;
uint32_t idx;
do
{
kprintf("head.start 0x%llx\n", head->start);
kprintf("head.size 0x%llx\n", head->size);
kprintf("head.end 0x%llx\n", head->end);
kprintf("head.alignment 0x%llx\n", head->alignment);
kprintf("allocs:\n");
range = head->allocations;
idx = 0;
while (true)
{
if (range == (IOPCIRange *) &head->end)
{
kprintf("[end]\n");
break;
}
kprintf("[%d].start 0x%llx\n", idx, range->start);
kprintf("[%d].size 0x%llx\n", idx, range->size);
kprintf("[%d].end 0x%llx\n", idx, range->end);
kprintf("[%d].alignment 0x%llx\n", idx, range->alignment);
idx++;
range = range->nextSubRange;
}
kprintf("------\n");
}
while ((head = head->next));
kprintf("------------------------------------\n");
}
#ifndef KERNEL
int main(int argc, char **argv)
{
IOPCIRange * head = NULL;
IOPCIRange * range;
IOPCIRange * requests = NULL;
IOPCIRange * elems[8];
IOPCIScalar shrink;
size_t idx;
bool ok;
for (idx = 0; idx < sizeof(elems) / sizeof(elems[0]); idx++)
{
elems[idx] = IOPCIRangeAlloc();
elems[idx]->maxAddress = 0xFFFFFFFFFFFFFFFFULL;
}
IOPCIRangeListAddRange(&head, 0, 0x6, 0xfa, 1);
IOPCIRangeDump(head);
range = elems[4];
range->start = 0x06;
range->proposedSize = 0x01;
range->alignment = 1;
ok = IOPCIRangeListAllocateSubRange(head, range);
assert(ok);
range = elems[3];
range->start = 0x07;
range->proposedSize = 0x01;
range->alignment = 1;
ok = IOPCIRangeListAllocateSubRange(head, range);
assert(ok);
range = elems[1];
range->start = 1*0x85;
range->proposedSize = 0x17;
range->alignment = 1;
range->flags = kIOPCIRangeFlagSplay;
ok = IOPCIRangeListAllocateSubRange(head, range);
assert(ok);
range = elems[2];
range->start = 0;
range->proposedSize = 2;
range->alignment = 1;
range->flags = kIOPCIRangeFlagSplay;
ok = IOPCIRangeListAllocateSubRange(head, range);
assert(ok);
range = elems[5];
range->start = 0;
range->proposedSize = 1;
range->alignment = 1;
range->flags = kIOPCIRangeFlagSplay;
ok = IOPCIRangeListAllocateSubRange(head, range);
assert(ok);
range = elems[6];
range->start = 0;
range->proposedSize = 1;
range->alignment = 1;
range->flags = kIOPCIRangeFlagSplay;
ok = IOPCIRangeListAllocateSubRange(head, range);
assert(ok);
IOPCIRangeDump(head);
exit(0);
shrink = IOPCIRangeListLastFree(head, 1024);
printf("IOPCIRangeListLastFree 0x%llx\n", shrink);
exit(0);
idx = 0;
IOPCIRangeInit(elems[idx++], 0, 0, 1024*1024);
range = elems[0];
ok = IOPCIRangeListAllocateSubRange(head, range);
printf("alloc(%d) [0x%llx, 0x%llx]\n", ok, range->start, range->size);
IOPCIRangeDump(head);
shrink = IOPCIRangeListCollapse(head, 1024*1024);
printf("Collapsed by 0x%llx\n", shrink);
IOPCIRangeDump(head);
exit(0);
IOPCIRangeListAddRange(&head, 0, 0xA0000000, 0x10000000);
IOPCIRangeListAddRange(&head, 0, 0x98000000, 0x08000000);
IOPCIRangeListAddRange(&head, 0, 0x90000000, 0x08000000);
IOPCIRangeListAddRange(&head, 0, 0xB0000000, 0x10000000);
idx = 0;
IOPCIRangeInit(elems[idx++], 0, 0x80001000, 0x1000);
IOPCIRangeInit(elems[idx++], 0, 0, 0x1000000);
IOPCIRangeInit(elems[idx++], 0, 0, 0x20000000);
IOPCIRangeInit(elems[idx++], 0, 0, 0x20000000);
IOPCIRangeInit(elems[idx++], 0, 0x80002000, 0x800);
IOPCIRangeInit(elems[idx++], 0, 0, 0x10000, 1);
for (idx = 0; idx < sizeof(elems) / sizeof(elems[0]); idx++)
{
if (elems[idx]->size)
IOPCIRangeAppendSubRange(&requests, elems[idx]);
}
printf("reqs:\n");
range = requests;
idx = 0;
while (range)
{
printf("[%ld].start 0x%llx\n", idx, range->start);
printf("[%ld].size 0x%llx\n", idx, range->size);
printf("[%ld].end 0x%llx\n", idx, range->end);
printf("[%ld].alignment 0x%llx\n", idx, range->alignment);
idx++;
range = range->nextSubRange;
}
while ((range = requests))
{
requests = range->nextSubRange;
ok = IOPCIRangeListAllocateSubRange(head, range);
printf("alloc(%d) [0x%llx, 0x%llx]\n", ok, range->start, range->size);
}
IOPCIRangeDump(head);
shrink = IOPCIRangeListCollapse(head, 1024*1024);
printf("Collapsed by 0x%llx\n", shrink);
IOPCIRangeDump(head);
exit(0);
for (idx = 0; idx < sizeof(elems) / sizeof(elems[0]); idx++)
{
range = elems[idx];
if (range->size && range->start)
{
ok = IOPCIRangeListDeallocateSubRange(head, range);
printf("dealloc(%d) [0x%llx, 0x%llx]\n", ok, range->start, range->size);
ok = IOPCIRangeListAllocateSubRange(head, range);
printf("alloc(%d) [0x%llx, 0x%llx]\n", ok, range->start, range->size);
}
}
range = elems[5];
range->proposedSize = 2 * range->size;
ok = IOPCIRangeListAllocateSubRange(head, range);
printf("extalloc(%d) [0x%llx, 0x%llx]\n", ok, range->start, range->size);
range = elems[0];
range->proposedSize = 2 * range->size;
ok = IOPCIRangeListAllocateSubRange(head, range);
printf("extalloc(%d) [0x%llx, 0x%llx]\n", ok, range->start, range->size);
range->proposedSize = 2 * range->size;
ok = IOPCIRangeListAllocateSubRange(head, range, range->start - range->size);
printf("extalloc(%d) [0x%llx, 0x%llx]\n", ok, range->start, range->size);
IOPCIRangeDump(head);
exit(0);
}
#endif