Return to IORangeAllocator.cpp CVS log

Up to [Apple XNU] / XNU / iokit / Kernel

Annotation of XNU/iokit/Kernel/IORangeAllocator.cpp, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 1998-2000 Apple Computer, Inc. All rights reserved.
        !             3:  *
        !             4:  * @APPLE_LICENSE_HEADER_START@
        !             5:  * 
        !             6:  * The contents of this file constitute Original Code as defined in and
        !             7:  * are subject to the Apple Public Source License Version 1.1 (the
        !             8:  * "License").  You may not use this file except in compliance with the
        !             9:  * License.  Please obtain a copy of the License at
        !            10:  * http://www.apple.com/publicsource and read it before using this file.
        !            11:  * 
        !            12:  * This Original Code and all software distributed under the License are
        !            13:  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
        !            14:  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
        !            15:  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
        !            16:  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
        !            17:  * License for the specific language governing rights and limitations
        !            18:  * under the License.
        !            19:  * 
        !            20:  * @APPLE_LICENSE_HEADER_END@
        !            21:  */
        !            22: /*
        !            23:  * Copyright (c) 1999 Apple Computer, Inc.
        !            24:  *
        !            25:  *
        !            26:  * HISTORY
        !            27:  *
        !            28:  * sdouglas 05 Nov 99 - created.
        !            29:  */
        !            30: 
        !            31: #include <libkern/c++/OSArray.h>
        !            32: #include <libkern/c++/OSNumber.h>
        !            33: #include <IOKit/IORangeAllocator.h>
        !            34: #include <IOKit/IOLib.h>
        !            35: #include <IOKit/IOLocks.h>
        !            36: #include <IOKit/assert.h>
        !            37: 
        !            38: /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
        !            39: 
        !            40: #undef super
        !            41: #define super OSObject
        !            42: 
        !            43: OSDefineMetaClassAndStructors( IORangeAllocator, OSObject )
        !            44: 
        !            45: struct IORangeAllocatorElement {
        !            46:     // closed range
        !            47:     IORangeScalar      start;
        !            48:     IORangeScalar      end;
        !            49: };
        !            50: 
        !            51: IOLock *       gIORangeAllocatorLock;
        !            52: 
        !            53: #define LOCK()         \
        !            54:        if( options & kLocking) IOTakeLock( gIORangeAllocatorLock )
        !            55: #define UNLOCK()       \
        !            56:        if( options & kLocking) IOUnlock( gIORangeAllocatorLock )
        !            57: 
        !            58: /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
        !            59: 
        !            60: bool IORangeAllocator::init( IORangeScalar endOfRange,
        !            61:                                IORangeScalar _defaultAlignment,
        !            62:                                UInt32 _capacity,
        !            63:                                IOOptionBits _options )
        !            64: {
        !            65:     if( !super::init())
        !            66:        return( false );
        !            67: 
        !            68:     if( !_capacity)
        !            69:        _capacity = 1;
        !            70:     if( !_defaultAlignment)
        !            71:        _defaultAlignment = 1;
        !            72:     capacity           = 0;
        !            73:     capacityIncrement  = _capacity;
        !            74:     numElements        = 0;
        !            75:     elements           = 0;
        !            76:     defaultAlignmentMask = _defaultAlignment - 1;
        !            77:     options            = _options;
        !            78: 
        !            79:     if( (!gIORangeAllocatorLock) && (options & kLocking))
        !            80:        gIORangeAllocatorLock = IOLockAlloc();
        !            81: 
        !            82:     if( endOfRange)
        !            83:        deallocate( 0, endOfRange + 1 );
        !            84: 
        !            85:     return( true );
        !            86: }
        !            87: 
        !            88: IORangeAllocator * IORangeAllocator:: withRange(
        !            89:                                        IORangeScalar endOfRange,
        !            90:                                        IORangeScalar defaultAlignment = 0,
        !            91:                                        UInt32 capacity = 0,
        !            92:                                        IOOptionBits options = 0 )
        !            93: {
        !            94:     IORangeAllocator * thingy;
        !            95: 
        !            96:     thingy = new IORangeAllocator;
        !            97:     if( thingy && ! thingy->init( endOfRange, defaultAlignment,
        !            98:                                capacity, options )) {
        !            99:        thingy->release();
        !           100:        thingy = 0;
        !           101:     }
        !           102: 
        !           103:     return( thingy );
        !           104: }
        !           105: 
        !           106: void IORangeAllocator::free()
        !           107: {
        !           108:     if( elements)
        !           109:        IODelete( elements, IORangeAllocatorElement, capacity );
        !           110: 
        !           111:     super::free();
        !           112: }
        !           113: 
        !           114: UInt32 IORangeAllocator::getFragmentCount( void )
        !           115: {
        !           116:     return( numElements );
        !           117: }
        !           118: 
        !           119: UInt32 IORangeAllocator::getFragmentCapacity( void )
        !           120: {
        !           121:     return( capacity );
        !           122: }
        !           123: 
        !           124: void IORangeAllocator::setFragmentCapacityIncrement( UInt32 count )
        !           125: {
        !           126:     capacityIncrement = count;
        !           127: }
        !           128: 
        !           129: 
        !           130: // allocate element at index
        !           131: bool IORangeAllocator::allocElement( UInt32 index )
        !           132: {
        !           133:     UInt32                     newCapacity;
        !           134:     IORangeAllocatorElement *  newElements;
        !           135: 
        !           136:     if( ((numElements == capacity) && capacityIncrement)
        !           137:      || (!elements)) {
        !           138: 
        !           139:        newCapacity = capacity + capacityIncrement;
        !           140:        newElements = IONew( IORangeAllocatorElement, newCapacity );
        !           141:        if( !newElements)
        !           142:            return( false );
        !           143: 
        !           144:        if( elements) {
        !           145:            bcopy( elements,
        !           146:                   newElements,
        !           147:                   index * sizeof( IORangeAllocatorElement));
        !           148:            bcopy( elements + index,
        !           149:                   newElements + index + 1,
        !           150:                   (numElements - index) * sizeof( IORangeAllocatorElement));
        !           151: 
        !           152:            IODelete( elements, IORangeAllocatorElement, capacity );
        !           153:        }
        !           154: 
        !           155:        elements = newElements;
        !           156:        capacity = newCapacity;
        !           157: 
        !           158:     } else {
        !           159: 
        !           160:        bcopy( elements + index,
        !           161:               elements + index + 1,
        !           162:               (numElements - index) * sizeof( IORangeAllocatorElement));
        !           163:     }
        !           164:     numElements++;
        !           165: 
        !           166:     return( true );
        !           167: }
        !           168: 
        !           169: // destroy element at index
        !           170: void IORangeAllocator::deallocElement( UInt32 index )
        !           171: {
        !           172:     numElements--;
        !           173:     bcopy( elements + index + 1,
        !           174:           elements + index,
        !           175:           (numElements - index) * sizeof( IORangeAllocatorElement));
        !           176: }
        !           177: 
        !           178: bool IORangeAllocator::allocate( IORangeScalar size,
        !           179:                                 IORangeScalar * result,
        !           180:                                 IORangeScalar alignment = 0 )
        !           181: {
        !           182:     IORangeScalar      data, dataEnd;
        !           183:     IORangeScalar      thisStart, thisEnd;
        !           184:     UInt32             index;
        !           185:     bool               ok = false;
        !           186: 
        !           187:     if( !size || !result)
        !           188:        return( false );
        !           189: 
        !           190:     if( 0 == alignment)
        !           191:        alignment = defaultAlignmentMask;
        !           192:     else
        !           193:         alignment--;
        !           194: 
        !           195:     size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
        !           196: 
        !           197:     LOCK();
        !           198: 
        !           199:     for( index = 0; index < numElements; index++ ) {
        !           200: 
        !           201:        thisStart = elements[index].start;
        !           202:        thisEnd = elements[index].end;
        !           203:         data = (thisStart + alignment) & ~alignment;
        !           204:        dataEnd = (data + size - 1);
        !           205: 
        !           206:        ok = (dataEnd <= thisEnd);
        !           207:        if( ok) {
        !           208:            if( data != thisStart) {
        !           209:                if( dataEnd != thisEnd) {
        !           210:                    if( allocElement( index + 1 )) {
        !           211:                        elements[index++].end = data - 1;
        !           212:                        elements[index].start = dataEnd + 1;
        !           213:                        elements[index].end = thisEnd;
        !           214:                    } else
        !           215:                        ok = false;
        !           216:                } else
        !           217:                    elements[index].end = data - 1;
        !           218:            } else {
        !           219:                if( dataEnd != thisEnd)
        !           220:                    elements[index].start = dataEnd + 1;
        !           221:                else
        !           222:                    deallocElement( index );
        !           223:            }
        !           224:            if( ok)
        !           225:                *result = data;
        !           226:            break;
        !           227:        } 
        !           228:     }
        !           229: 
        !           230:     UNLOCK();
        !           231: 
        !           232:     return( ok );
        !           233: }
        !           234: 
        !           235: bool IORangeAllocator::allocateRange( IORangeScalar data,
        !           236:                                         IORangeScalar size )
        !           237: {
        !           238:     IORangeScalar      thisStart, thisEnd;
        !           239:     IORangeScalar      dataEnd;
        !           240:     UInt32             index;
        !           241:     bool               found = false;
        !           242: 
        !           243:     if( !size)
        !           244:        return( 0 );
        !           245: 
        !           246:     size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
        !           247:     dataEnd = data + size - 1;
        !           248: 
        !           249:     LOCK();
        !           250: 
        !           251:     for( index = 0;
        !           252:         (!found) && (index < numElements);
        !           253:         index++ ) {
        !           254: 
        !           255:        thisStart = elements[index].start;
        !           256:        thisEnd = elements[index].end;
        !           257: 
        !           258:        if( thisStart > data)
        !           259:            break;
        !           260:        found = (dataEnd <= thisEnd);
        !           261: 
        !           262:         if( found) {
        !           263:            if( data != thisStart) {
        !           264:                if( dataEnd != thisEnd) {
        !           265:                    found = allocElement( index + 1 );
        !           266:                    if( found) {
        !           267:                        elements[index++].end = data - 1;
        !           268:                        elements[index].start = dataEnd + 1;
        !           269:                        elements[index].end = thisEnd;
        !           270:                    }
        !           271:                } else
        !           272:                    elements[index].end = data - 1;
        !           273:            } else if( dataEnd != thisEnd)
        !           274:                elements[index].start = dataEnd + 1;
        !           275:            else
        !           276:                deallocElement( index );
        !           277:         }
        !           278:     }
        !           279: 
        !           280:     UNLOCK();
        !           281: 
        !           282:     return( found );
        !           283: }
        !           284: 
        !           285: void IORangeAllocator::deallocate( IORangeScalar data,
        !           286:                                   IORangeScalar size )
        !           287: {
        !           288:     IORangeScalar      dataEnd;
        !           289:     UInt32             index;
        !           290:     bool               headContig = false;
        !           291:     bool               tailContig = false;
        !           292: 
        !           293:     size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
        !           294:     dataEnd = data + size - 1;
        !           295: 
        !           296:     LOCK();
        !           297: 
        !           298:     for( index = 0; index < numElements; index++ ) {
        !           299:        if( elements[index].start < data) {
        !           300:            headContig = (data <= (elements[index].end + 1));
        !           301:            continue;
        !           302:        }
        !           303:        tailContig = ((data + size) >= elements[index].start);
        !           304:        break;
        !           305:     }
        !           306: 
        !           307:     if( headContig) {
        !           308:         if( tailContig) {
        !           309:             elements[index-1].end = elements[index].end;
        !           310:            deallocElement( index );
        !           311:        } else /*safe*/ if( dataEnd > elements[index-1].end)
        !           312:            elements[index-1].end = dataEnd;
        !           313: 
        !           314:     } else if( tailContig) {
        !           315:        if( data < elements[index].start) /*safe*/
        !           316:            elements[index].start = data;
        !           317: 
        !           318:     } else if( allocElement( index)) {
        !           319:        elements[index].start = data;
        !           320:        elements[index].end = dataEnd;
        !           321:     }
        !           322: 
        !           323:     UNLOCK();
        !           324: }
        !           325: 
        !           326: bool IORangeAllocator::serialize(OSSerialize *s) const
        !           327: {
        !           328:     OSArray *  array = OSArray::withCapacity( numElements * 2 );
        !           329:     OSNumber * num;
        !           330:     UInt32     index;
        !           331:     bool       ret;
        !           332: 
        !           333:     if( !array)
        !           334:        return( false );
        !           335: 
        !           336:     LOCK();
        !           337: 
        !           338:     for( index = 0; index < numElements; index++) {
        !           339:        if( (num = OSNumber::withNumber( elements[index].start,
        !           340:                                        8 * sizeof(IORangeScalar) ))) {
        !           341:            array->setObject(num);
        !           342:            num->release();
        !           343:        }
        !           344:        if( (num = OSNumber::withNumber( elements[index].end,
        !           345:                                        8 * sizeof(IORangeScalar) ))) {
        !           346:            array->setObject(num);
        !           347:            num->release();
        !           348:        }
        !           349:     }
        !           350: 
        !           351:     UNLOCK();
        !           352: 
        !           353:     ret = array->serialize(s);
        !           354:     array->release();
        !           355: 
        !           356:     return( ret );
        !           357: }
        !           358: 
        !           359: IORangeScalar IORangeAllocator::getFreeCount( void )
        !           360: {
        !           361:     UInt32             index;
        !           362:     IORangeScalar      sum = 0;
        !           363: 
        !           364:     for( index = 0; index < numElements; index++)
        !           365:        sum += elements[index].end - elements[index].start + 1;
        !           366: 
        !           367:     return( sum );
        !           368: }
        !           369: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.