IORangeAllocator.cpp [plain text]
#include <libkern/c++/OSArray.h>
#include <libkern/c++/OSNumber.h>
#include <IOKit/IORangeAllocator.h>
#include <IOKit/IOLib.h>
#include <IOKit/IOLocks.h>
#include <IOKit/assert.h>
#undef super
#define super OSObject
OSDefineMetaClassAndStructors( IORangeAllocator, OSObject )
struct IORangeAllocatorElement {
IORangeScalar start;
IORangeScalar end;
};
IOLock * gIORangeAllocatorLock;
#define LOCK() \
if( options & kLocking) IOTakeLock( gIORangeAllocatorLock )
#define UNLOCK() \
if( options & kLocking) IOUnlock( gIORangeAllocatorLock )
bool IORangeAllocator::init( IORangeScalar endOfRange,
IORangeScalar _defaultAlignment,
UInt32 _capacity,
IOOptionBits _options )
{
if( !super::init())
return( false );
if( !_capacity)
_capacity = 1;
if( !_defaultAlignment)
_defaultAlignment = 1;
capacity = 0;
capacityIncrement = _capacity;
numElements = 0;
elements = 0;
defaultAlignmentMask = _defaultAlignment - 1;
options = _options;
if( (!gIORangeAllocatorLock) && (options & kLocking))
gIORangeAllocatorLock = IOLockAlloc();
if( endOfRange)
deallocate( 0, endOfRange + 1 );
return( true );
}
IORangeAllocator * IORangeAllocator:: withRange(
IORangeScalar endOfRange,
IORangeScalar defaultAlignment,
UInt32 capacity,
IOOptionBits options )
{
IORangeAllocator * thingy;
thingy = new IORangeAllocator;
if( thingy && ! thingy->init( endOfRange, defaultAlignment,
capacity, options )) {
thingy->release();
thingy = 0;
}
return( thingy );
}
void IORangeAllocator::free()
{
if( elements)
IODelete( elements, IORangeAllocatorElement, capacity );
super::free();
}
UInt32 IORangeAllocator::getFragmentCount( void )
{
return( numElements );
}
UInt32 IORangeAllocator::getFragmentCapacity( void )
{
return( capacity );
}
void IORangeAllocator::setFragmentCapacityIncrement( UInt32 count )
{
capacityIncrement = count;
}
bool IORangeAllocator::allocElement( UInt32 index )
{
UInt32 newCapacity;
IORangeAllocatorElement * newElements;
if( ((numElements == capacity) && capacityIncrement)
|| (!elements)) {
newCapacity = capacity + capacityIncrement;
newElements = IONew( IORangeAllocatorElement, newCapacity );
if( !newElements)
return( false );
if( elements) {
bcopy( elements,
newElements,
index * sizeof( IORangeAllocatorElement));
bcopy( elements + index,
newElements + index + 1,
(numElements - index) * sizeof( IORangeAllocatorElement));
IODelete( elements, IORangeAllocatorElement, capacity );
}
elements = newElements;
capacity = newCapacity;
} else {
bcopy( elements + index,
elements + index + 1,
(numElements - index) * sizeof( IORangeAllocatorElement));
}
numElements++;
return( true );
}
void IORangeAllocator::deallocElement( UInt32 index )
{
numElements--;
bcopy( elements + index + 1,
elements + index,
(numElements - index) * sizeof( IORangeAllocatorElement));
}
bool IORangeAllocator::allocate( IORangeScalar size,
IORangeScalar * result,
IORangeScalar alignment )
{
IORangeScalar data, dataEnd;
IORangeScalar thisStart, thisEnd;
UInt32 index;
bool ok = false;
if( !size || !result)
return( false );
if( 0 == alignment)
alignment = defaultAlignmentMask;
else
alignment--;
size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
LOCK();
for( index = 0; index < numElements; index++ ) {
thisStart = elements[index].start;
thisEnd = elements[index].end;
data = (thisStart + alignment) & ~alignment;
dataEnd = (data + size - 1);
ok = (dataEnd <= thisEnd);
if( ok) {
if( data != thisStart) {
if( dataEnd != thisEnd) {
if( allocElement( index + 1 )) {
elements[index++].end = data - 1;
elements[index].start = dataEnd + 1;
elements[index].end = thisEnd;
} else
ok = false;
} else
elements[index].end = data - 1;
} else {
if( dataEnd != thisEnd)
elements[index].start = dataEnd + 1;
else
deallocElement( index );
}
if( ok)
*result = data;
break;
}
}
UNLOCK();
return( ok );
}
bool IORangeAllocator::allocateRange( IORangeScalar data,
IORangeScalar size )
{
IORangeScalar thisStart, thisEnd;
IORangeScalar dataEnd;
UInt32 index;
bool found = false;
if( !size)
return( 0 );
size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
dataEnd = data + size - 1;
LOCK();
for( index = 0;
(!found) && (index < numElements);
index++ ) {
thisStart = elements[index].start;
thisEnd = elements[index].end;
if( thisStart > data)
break;
found = (dataEnd <= thisEnd);
if( found) {
if( data != thisStart) {
if( dataEnd != thisEnd) {
found = allocElement( index + 1 );
if( found) {
elements[index++].end = data - 1;
elements[index].start = dataEnd + 1;
elements[index].end = thisEnd;
}
} else
elements[index].end = data - 1;
} else if( dataEnd != thisEnd)
elements[index].start = dataEnd + 1;
else
deallocElement( index );
}
}
UNLOCK();
return( found );
}
void IORangeAllocator::deallocate( IORangeScalar data,
IORangeScalar size )
{
IORangeScalar dataEnd;
UInt32 index;
bool headContig = false;
bool tailContig = false;
size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
dataEnd = data + size - 1;
LOCK();
for( index = 0; index < numElements; index++ ) {
if( elements[index].start < data) {
headContig = (data <= (elements[index].end + 1));
continue;
}
tailContig = ((data + size) >= elements[index].start);
break;
}
if( headContig) {
if( tailContig) {
elements[index-1].end = elements[index].end;
deallocElement( index );
} else if( dataEnd > elements[index-1].end)
elements[index-1].end = dataEnd;
} else if( tailContig) {
if( data < elements[index].start)
elements[index].start = data;
} else if( allocElement( index)) {
elements[index].start = data;
elements[index].end = dataEnd;
}
UNLOCK();
}
bool IORangeAllocator::serialize(OSSerialize *s) const
{
OSArray * array = OSArray::withCapacity( numElements * 2 );
OSNumber * num;
UInt32 index;
bool ret;
if( !array)
return( false );
LOCK();
for( index = 0; index < numElements; index++) {
if( (num = OSNumber::withNumber( elements[index].start,
8 * sizeof(IORangeScalar) ))) {
array->setObject(num);
num->release();
}
if( (num = OSNumber::withNumber( elements[index].end,
8 * sizeof(IORangeScalar) ))) {
array->setObject(num);
num->release();
}
}
UNLOCK();
ret = array->serialize(s);
array->release();
return( ret );
}
IORangeScalar IORangeAllocator::getFreeCount( void )
{
UInt32 index;
IORangeScalar sum = 0;
for( index = 0; index < numElements; index++)
sum += elements[index].end - elements[index].start + 1;
return( sum );
}