IORangeAllocator.cpp

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

FreeBSD/Linux Kernel Cross Reference
sys/iokit/Kernel/IORangeAllocator.cpp
