arb.c 107 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308330933103311331233133314331533163317331833193320332133223323332433253326332733283329333033313332333333343335333633373338333933403341334233433344334533463347334833493350335133523353335433553356335733583359336033613362336333643365336633673368336933703371337233733374337533763377337833793380338133823383338433853386338733883389339033913392339333943395339633973398339934003401340234033404340534063407340834093410341134123413341434153416341734183419342034213422342334243425342634273428342934303431343234333434343534363437343834393440344134423443344434453446344734483449345034513452345334543455345634573458345934603461346234633464346534663467346834693470347134723473347434753476347734783479348034813482348334843485348634873488348934903491349234933494349534963497349834993500350135023503350435053506350735083509351035113512351335143515351635173518351935203521352235233524352535263527352835293530353135323533353435353536353735383539354035413542354335443545354635473548354935503551355235533554355535563557355835593560356135623563356435653566356735683569357035713572357335743575357635773578357935803581358235833584358535863587358835893590359135923593359435953596359735983599360036013602360336043605360636073608360936103611361236133614361536163617361836193620362136223623362436253626362736283629363036313632363336343635363636373638363936403641364236433644364536463647364836493650365136523653365436553656365736583659366036613662366336643665366636673668366936703671367236733674367536763677367836793680368136823683368436853686368736883689369036913692369336943695369636973698369937003701370237033704370537063707370837093710371137123713371437153716371737183719372037213722372337243725372637273728372937303731373237333734373537363737373837393740374137423743374437453746374737483749375037513752375337543755375637573758375937603761376237633764376537663767376837693770377137723773377437753776377737783779378037813782378337843785378637873788378937903791379237933794379537963797379837993800380138023803380438053806380738083809381038113812381338143815381638173818381938203821382238233824382538263827382838293830383138323833383438353836383738383839384038413842384338443845384638473848384938503851385238533854385538563857385838593860386138623863386438653866386738683869387038713872387338743875387638773878387938803881388238833884388538863887388838893890389138923893389438953896389738983899390039013902390339043905390639073908390939103911391239133914391539163917391839193920392139223923392439253926392739283929393039313932393339343935393639373938393939403941394239433944394539463947394839493950395139523953395439553956395739583959396039613962396339643965396639673968396939703971397239733974397539763977397839793980398139823983398439853986398739883989399039913992399339943995399639973998399940004001400240034004400540064007400840094010401140124013401440154016401740184019402040214022402340244025402640274028402940304031403240334034403540364037403840394040
  1. /*++
  2. Copyright (c) 2012 Minoca Corp. All Rights Reserved
  3. Module Name:
  4. arb.c
  5. Abstract:
  6. This module implements support for system resource arbiters.
  7. Author:
  8. Evan Green 2-Dec-2012
  9. Environment:
  10. Kernel
  11. --*/
  12. //
  13. // ------------------------------------------------------------------- Includes
  14. //
  15. #include <minoca/kernel/kernel.h>
  16. #include "iop.h"
  17. #include "arb.h"
  18. //
  19. // ---------------------------------------------------------------- Definitions
  20. //
  21. //
  22. // Set this flag to make the arbiter print out all requirement and allocation
  23. // lists.
  24. //
  25. #define ARBITER_DEBUG_PRINT_RESOURCES 0x00000001
  26. //
  27. // ------------------------------------------------------ Data Type Definitions
  28. //
  29. //
  30. // ----------------------------------------------- Internal Function Prototypes
  31. //
  32. KSTATUS
  33. IopFinalizeResourceAllocation (
  34. PDEVICE Device
  35. );
  36. KSTATUS
  37. IopArbiterAddFreeSpace (
  38. PRESOURCE_ARBITER Arbiter,
  39. ULONGLONG FreeSpaceBegin,
  40. ULONGLONG FreeSpaceLength,
  41. ULONGLONG FreeSpaceCharacteristics,
  42. PRESOURCE_ALLOCATION SourcingAllocation,
  43. ULONGLONG TranslationOffset
  44. );
  45. KSTATUS
  46. IopArbiterAllocateSpace (
  47. PARBITER_ALLOCATION_CONTEXT Context,
  48. UINTN RequirementIndex,
  49. PRESOURCE_REQUIREMENT Alternative
  50. );
  51. KSTATUS
  52. IopArbiterInsertEntry (
  53. PRESOURCE_ARBITER Arbiter,
  54. ARBITER_SPACE_TYPE SpaceType,
  55. PDEVICE ClaimingDevice,
  56. ULONGLONG Allocation,
  57. ULONGLONG Length,
  58. ULONGLONG Characteristics,
  59. ULONG Flags,
  60. PRESOURCE_REQUIREMENT RootRequirement,
  61. PARBITER_ENTRY ExistingEntry,
  62. PARBITER_ENTRY *NewEntry
  63. );
  64. VOID
  65. IopArbiterFreeEntry (
  66. PRESOURCE_ARBITER Arbiter,
  67. PARBITER_ENTRY Entry
  68. );
  69. VOID
  70. IopArbiterDestroy (
  71. PRESOURCE_ARBITER Arbiter
  72. );
  73. PRESOURCE_ARBITER
  74. IopArbiterFindArbiter (
  75. PDEVICE Device,
  76. RESOURCE_TYPE ResourceType
  77. );
  78. PARBITER_ENTRY
  79. IopArbiterFindEntry (
  80. PRESOURCE_ARBITER Arbiter,
  81. ULONGLONG Allocation,
  82. BOOL DependentEntryPreferred
  83. );
  84. VOID
  85. IopArbiterAddRequirement (
  86. PARBITER_ALLOCATION_CONTEXT Context,
  87. PRESOURCE_REQUIREMENT Requirement,
  88. PDEVICE Device
  89. );
  90. KSTATUS
  91. IopArbiterInitializeAllocationContext (
  92. PDEVICE Device,
  93. PARBITER_ALLOCATION_CONTEXT *NewContext
  94. );
  95. VOID
  96. IopArbiterDestroyAllocationContext (
  97. PARBITER_ALLOCATION_CONTEXT Context
  98. );
  99. KSTATUS
  100. IopArbiterSatisfyAllocationContext (
  101. PARBITER_ALLOCATION_CONTEXT Context
  102. );
  103. VOID
  104. IopArbiterSortRequirements (
  105. PARBITER_ALLOCATION_CONTEXT Context
  106. );
  107. BOOL
  108. IopArbiterIsFirstRequirementHigherPriority (
  109. PRESOURCE_REQUIREMENT FirstRequirement,
  110. PRESOURCE_REQUIREMENT SecondRequirement
  111. );
  112. KSTATUS
  113. IopArbiterRipUpReservedAllocations (
  114. PARBITER_ALLOCATION_CONTEXT Context
  115. );
  116. KSTATUS
  117. IopArbiterExpandFailingArbiters (
  118. PARBITER_ALLOCATION_CONTEXT Context
  119. );
  120. KSTATUS
  121. IopArbiterExpandSpace (
  122. PRESOURCE_ARBITER Arbiter,
  123. ULONGLONG AmountNeeded
  124. );
  125. KSTATUS
  126. IopArbiterLimitResourceHog (
  127. PARBITER_ALLOCATION_CONTEXT Context
  128. );
  129. KSTATUS
  130. IopArbiterResizeAllocationContext (
  131. PARBITER_ALLOCATION_CONTEXT Context,
  132. ULONG NewDeviceCount,
  133. ULONG NewRequirementCount
  134. );
  135. VOID
  136. IopArbiterMarkSelectedConfigurations (
  137. PARBITER_ALLOCATION_CONTEXT Context
  138. );
  139. VOID
  140. IopArbiterMatchAllocationsToRequirements (
  141. PDEVICE Device,
  142. PULONG RequirementCount
  143. );
  144. VOID
  145. IopArbiterInitializeResourceAllocation (
  146. PARBITER_ENTRY ArbiterEntry,
  147. PRESOURCE_ALLOCATION ResourceAllocation
  148. );
  149. KSTATUS
  150. IopArbiterCopyAndTranslateResources (
  151. PRESOURCE_ALLOCATION_LIST BusLocalResources,
  152. PRESOURCE_ALLOCATION_LIST *ProcessorLocalResources
  153. );
  154. KSTATUS
  155. IopArbiterTryBootAllocations (
  156. PARBITER_ALLOCATION_CONTEXT Context
  157. );
  158. KSTATUS
  159. IopArbiterTryBootAllocation (
  160. PARBITER_ALLOCATION_CONTEXT Context,
  161. UINTN RequirementIndex
  162. );
  163. PRESOURCE_ALLOCATION
  164. IopArbiterFindBootAllocationForRequirement (
  165. PDEVICE Device,
  166. PRESOURCE_REQUIREMENT Requirement
  167. );
  168. VOID
  169. IopArbiterClearContextAllocations (
  170. PARBITER_ALLOCATION_CONTEXT Context
  171. );
  172. VOID
  173. IopArbiterLinkContextAllocations (
  174. PARBITER_ALLOCATION_CONTEXT Context
  175. );
  176. KSTATUS
  177. IopDeferResourceAllocation (
  178. PDEVICE Device
  179. );
  180. //
  181. // -------------------------------------------------------------------- Globals
  182. //
  183. //
  184. // Set this value to something nonzero in the debugger to enable arbiter debug
  185. // options. See ARBITER_DEBUG_* definitions.
  186. //
  187. ULONG IoArbiterDebugOptions = 0;
  188. //
  189. // ------------------------------------------------------------------ Functions
  190. //
  191. KERNEL_API
  192. KSTATUS
  193. IoCreateResourceArbiter (
  194. PDEVICE Device,
  195. RESOURCE_TYPE ResourceType
  196. )
  197. /*++
  198. Routine Description:
  199. This routine creates a resource arbiter for the given bus device between
  200. a system resource and the device's children. This function is needed for
  201. any device whose children access system resources (like physical address
  202. space) through a window set up by the parent.
  203. Arguments:
  204. Device - Supplies a pointer to the parent bus device that provides
  205. resources.
  206. ResourceType - Supplies the type of resource that the device provides.
  207. Return Value:
  208. STATUS_SUCCESS if the new arbiter was created.
  209. STATUS_INVALID_PARAMETER if an invalid resource type was specified.
  210. STATUS_INSUFFICIENT_RESOURCES on allocation failure.
  211. STATUS_ALREADY_INITIALIZED if the device has already has a resource arbiter
  212. of this type.
  213. --*/
  214. {
  215. PRESOURCE_ARBITER Arbiter;
  216. PLIST_ENTRY CurrentEntry;
  217. PRESOURCE_ARBITER Existing;
  218. KSTATUS Status;
  219. Arbiter = NULL;
  220. if ((ResourceType == ResourceTypeInvalid) ||
  221. (ResourceType >= ResourceTypeCount)) {
  222. Status = STATUS_INVALID_PARAMETER;
  223. goto CreateResourceArbiterEnd;
  224. }
  225. //
  226. // Look for an existing one.
  227. //
  228. CurrentEntry = Device->ArbiterListHead.Next;
  229. while (CurrentEntry != &(Device->ArbiterListHead)) {
  230. Existing = LIST_VALUE(CurrentEntry, RESOURCE_ARBITER, ListEntry);
  231. CurrentEntry = CurrentEntry->Next;
  232. if (Existing->ResourceType == ResourceType) {
  233. Status = STATUS_ALREADY_INITIALIZED;
  234. goto CreateResourceArbiterEnd;
  235. }
  236. }
  237. //
  238. // Create the arbiter.
  239. //
  240. Arbiter = MmAllocatePagedPool(sizeof(RESOURCE_ARBITER),
  241. ARBITER_ALLOCATION_TAG);
  242. if (Arbiter == NULL) {
  243. Status = STATUS_INSUFFICIENT_RESOURCES;
  244. goto CreateResourceArbiterEnd;
  245. }
  246. //
  247. // Initialize and attach the arbiter.
  248. //
  249. RtlZeroMemory(Arbiter, sizeof(RESOURCE_ARBITER));
  250. Arbiter->OwningDevice = Device;
  251. Arbiter->ResourceType = ResourceType;
  252. INITIALIZE_LIST_HEAD(&(Arbiter->EntryListHead));
  253. INSERT_AFTER(&(Arbiter->ListEntry), &(Device->ArbiterListHead));
  254. Status = STATUS_SUCCESS;
  255. CreateResourceArbiterEnd:
  256. if (!KSUCCESS(Status)) {
  257. if (Arbiter != NULL) {
  258. MmFreePagedPool(Arbiter);
  259. }
  260. }
  261. return Status;
  262. }
  263. KERNEL_API
  264. KSTATUS
  265. IoDestroyResourceArbiter (
  266. PDEVICE Device,
  267. RESOURCE_TYPE ResourceType
  268. )
  269. /*++
  270. Routine Description:
  271. This routine destroys all resource arbiters for the given bus device that
  272. have the provided resource type.
  273. Arguments:
  274. Device - Supplies a pointer to the device that owns resource arbitration.
  275. ResourceType - Supplies the type of resource arbiter that is to be
  276. destroyed.
  277. Return Value:
  278. Status code.
  279. --*/
  280. {
  281. PRESOURCE_ARBITER Arbiter;
  282. //
  283. // Find the arbiter. If no arbiter is found, the device is trying to
  284. // destroy a region without creating an arbiter.
  285. //
  286. Arbiter = IopArbiterFindArbiter(Device, ResourceType);
  287. if (Arbiter == NULL) {
  288. return STATUS_INVALID_PARAMETER;
  289. }
  290. ASSERT(Arbiter->OwningDevice == Device);
  291. //
  292. // Destroy the arbiter. This will remove the arbiter from the device's
  293. // arbiter list.
  294. //
  295. IopArbiterDestroy(Arbiter);
  296. return STATUS_SUCCESS;
  297. }
  298. KERNEL_API
  299. KSTATUS
  300. IoAddFreeSpaceToArbiter (
  301. PDEVICE Device,
  302. RESOURCE_TYPE ResourceType,
  303. ULONGLONG FreeSpaceBegin,
  304. ULONGLONG FreeSpaceLength,
  305. ULONGLONG FreeSpaceCharacteristics,
  306. PRESOURCE_ALLOCATION SourcingAllocation,
  307. ULONGLONG TranslationOffset
  308. )
  309. /*++
  310. Routine Description:
  311. This routine adds a regions of allocatable space to a previously created
  312. resource arbiter.
  313. Arguments:
  314. Device - Supplies a pointer to the device that owns the arbiter (and the
  315. free space).
  316. ResourceType - Supplies the resource type that the arbiter can dole out.
  317. An arbiter of this type must have been created by the device.
  318. FreeSpaceBegin - Supplies the first address of the free region.
  319. FreeSpaceLength - Supplies the length of the free region.
  320. FreeSpaceCharacteristics - Supplies the characteristics of the free
  321. region.
  322. SourcingAllocation - Supplies a pointer to the parent resource allocation
  323. that makes this range possible. This pointer is optional. Supplying
  324. NULL here implies that the given resource is fixed in nature and
  325. cannot be expanded.
  326. TranslationOffset - Supplies the offset that has to be added to all
  327. doled out allocations on the secondary side to get an address in the
  328. source allocation space (primary side).
  329. To recap: SecondaryAddress + TranslationOffset = PrimaryAddress, where
  330. PrimaryAddress is closer to the CPU complex.
  331. Return Value:
  332. Status code.
  333. --*/
  334. {
  335. PRESOURCE_ARBITER Arbiter;
  336. KSTATUS Status;
  337. //
  338. // Find the arbiter. If no arbiter is found, the device is trying to add a
  339. // region without creating an arbiter.
  340. //
  341. Arbiter = IopArbiterFindArbiter(Device, ResourceType);
  342. if (Arbiter == NULL) {
  343. return STATUS_INVALID_PARAMETER;
  344. }
  345. if (FreeSpaceLength == 0) {
  346. return STATUS_SUCCESS;
  347. }
  348. Status = IopArbiterAddFreeSpace(Arbiter,
  349. FreeSpaceBegin,
  350. FreeSpaceLength,
  351. FreeSpaceCharacteristics,
  352. SourcingAllocation,
  353. TranslationOffset);
  354. return Status;
  355. }
  356. KERNEL_API
  357. PRESOURCE_ALLOCATION_LIST
  358. IoGetProcessorLocalResources (
  359. PDEVICE Device
  360. )
  361. /*++
  362. Routine Description:
  363. This routine returns the given device's processor local resources.
  364. Arguments:
  365. Device - Supplies a pointer to the device that owns the resources.
  366. Return Value:
  367. Returns a pointer to the processor local resource allocation list.
  368. --*/
  369. {
  370. return Device->ProcessorLocalResources;
  371. }
  372. KSTATUS
  373. IopProcessResourceRequirements (
  374. PDEVICE Device
  375. )
  376. /*++
  377. Routine Description:
  378. This routine attempts to find the best set of resources for a given device.
  379. Arguments:
  380. Device - Supplies a pointer to the device that will be receiving the
  381. resource allocation.
  382. Return Value:
  383. Status code.
  384. --*/
  385. {
  386. PARBITER_ALLOCATION_CONTEXT Context;
  387. BOOL Deferred;
  388. KSTATUS Status;
  389. Deferred = FALSE;
  390. if ((IoArbiterDebugOptions & ARBITER_DEBUG_PRINT_RESOURCES) != 0) {
  391. RtlDebugPrint("Resource Requirements for %s:\n", Device->Header.Name);
  392. if (Device->ResourceRequirements != NULL) {
  393. IoDebugPrintResourceConfigurationList(Device->ResourceRequirements);
  394. }
  395. RtlDebugPrint("Boot Resources for %s:\n", Device->Header.Name);
  396. if (Device->BootResources != NULL) {
  397. IoDebugPrintResourceAllocationList(0, Device->BootResources);
  398. }
  399. }
  400. //
  401. // Set up an allocation context based on the resource requirements for this
  402. // device.
  403. //
  404. Status = IopArbiterInitializeAllocationContext(Device, &Context);
  405. if (!KSUCCESS(Status)) {
  406. goto ProcessResourceRequirementsEnd;
  407. }
  408. if ((Context->DeviceCount == 0) || (Context->RequirementCount == 0)) {
  409. goto ProcessResourceRequirementsEnd;
  410. }
  411. //
  412. // Try on the boot allocations for size first.
  413. //
  414. Status = IopArbiterTryBootAllocations(Context);
  415. if (KSUCCESS(Status)) {
  416. goto ProcessResourceRequirementsEnd;
  417. }
  418. //
  419. // If the boot allocations did not work and this is the first time through
  420. // resource assignment, then delay resource assignment of this device until
  421. // all devices that have boot resources have enumerated. That way devices
  422. // that happen to come up earlier don't trod on fixed regions of
  423. // motherboard devices for instance.
  424. //
  425. if ((Device->Flags & DEVICE_FLAG_NOT_USING_BOOT_RESOURCES) == 0) {
  426. Device->Flags |= DEVICE_FLAG_NOT_USING_BOOT_RESOURCES;
  427. Status = IopDeferResourceAllocation(Device);
  428. if (KSUCCESS(Status)) {
  429. Status = STATUS_NOT_READY;
  430. Deferred = TRUE;
  431. }
  432. goto ProcessResourceRequirementsEnd;
  433. }
  434. //
  435. // Start by simply processing the device's requirement list.
  436. //
  437. Status = IopArbiterSatisfyAllocationContext(Context);
  438. if (KSUCCESS(Status)) {
  439. goto ProcessResourceRequirementsEnd;
  440. }
  441. //
  442. // That didn't work out unfortunately. Gather up all reserved allocations
  443. // (allocations that worked but have not yet been handed out to drivers)
  444. // from the arbiters that failed.
  445. //
  446. Status = IopArbiterRipUpReservedAllocations(Context);
  447. if (!KSUCCESS(Status)) {
  448. goto ProcessResourceRequirementsEnd;
  449. }
  450. Status = IopArbiterSatisfyAllocationContext(Context);
  451. if (KSUCCESS(Status)) {
  452. goto ProcessResourceRequirementsEnd;
  453. }
  454. //
  455. // Unfortunately that wasn't enough either. Attempt to pause all devices
  456. // with committed resources on the sticky arbiters, rip up all reserved
  457. // allocations, and try again.
  458. //
  459. //
  460. // That didn't work either. Attempt to expand all failing arbiters.
  461. //
  462. Status = IopArbiterExpandFailingArbiters(Context);
  463. if (!KSUCCESS(Status)) {
  464. goto ProcessResourceRequirementsEnd;
  465. }
  466. //
  467. // That did all it could, now start knocking devices out of their ideal
  468. // configuration, and potentially out of the running altogether until
  469. // there are simply no more devices left.
  470. // TODO: Also set a timer so that eventually this loop will give up if
  471. // there are simply too many combinations to try.
  472. //
  473. while (Context->DeviceCount != 0) {
  474. Status = IopArbiterSatisfyAllocationContext(Context);
  475. if (KSUCCESS(Status)) {
  476. goto ProcessResourceRequirementsEnd;
  477. }
  478. Status = IopArbiterLimitResourceHog(Context);
  479. if (!KSUCCESS(Status)) {
  480. goto ProcessResourceRequirementsEnd;
  481. }
  482. }
  483. if (Context->DeviceCount == 0) {
  484. Status = STATUS_UNSUCCESSFUL;
  485. goto ProcessResourceRequirementsEnd;
  486. }
  487. ProcessResourceRequirementsEnd:
  488. //
  489. // On success, mark which configuration was chosen for each device.
  490. //
  491. if (KSUCCESS(Status)) {
  492. IopArbiterMarkSelectedConfigurations(Context);
  493. Status = IopFinalizeResourceAllocation(Device);
  494. if ((IoArbiterDebugOptions & ARBITER_DEBUG_PRINT_RESOURCES) != 0) {
  495. RtlDebugPrint("Processor Local Resources for %s:\n",
  496. Device->Header.Name);
  497. if (Device->ProcessorLocalResources != NULL) {
  498. IoDebugPrintResourceAllocationList(
  499. 0,
  500. Device->ProcessorLocalResources);
  501. }
  502. RtlDebugPrint("Bus Local Resources for %s:\n", Device->Header.Name);
  503. if (Device->BusLocalResources != NULL) {
  504. IoDebugPrintResourceAllocationList(0,
  505. Device->BusLocalResources);
  506. }
  507. RtlDebugPrint("\n");
  508. }
  509. } else {
  510. if ((IoArbiterDebugOptions & ARBITER_DEBUG_PRINT_RESOURCES) != 0) {
  511. if (Deferred != FALSE) {
  512. RtlDebugPrint("Deferring resource allocation for %s (%x).\n",
  513. Device->Header.Name,
  514. Device);
  515. } else {
  516. RtlDebugPrint("Failed to allocate resource for %s (%x). "
  517. "Status = %x\n\n",
  518. Device->Header.Name,
  519. Device,
  520. Status);
  521. }
  522. }
  523. }
  524. if (Context != NULL) {
  525. IopArbiterDestroyAllocationContext(Context);
  526. }
  527. return Status;
  528. }
  529. VOID
  530. IopDestroyArbiterList (
  531. PDEVICE Device
  532. )
  533. /*++
  534. Routine Description:
  535. This routine destroys the arbiter list of the given device.
  536. Arguments:
  537. Device - Supplies a pointer to a device whose arbiter list is to be
  538. destroyed.
  539. Return Value:
  540. None.
  541. --*/
  542. {
  543. PRESOURCE_ARBITER CurrentArbiter;
  544. PLIST_ENTRY CurrentEntry;
  545. //
  546. // Loop throught the list of arbiters, destroying each one in turn.
  547. //
  548. CurrentEntry = Device->ArbiterListHead.Next;
  549. while (CurrentEntry != &(Device->ArbiterListHead)) {
  550. CurrentArbiter = LIST_VALUE(CurrentEntry, RESOURCE_ARBITER, ListEntry);
  551. CurrentEntry = CurrentEntry->Next;
  552. IopArbiterDestroy(CurrentArbiter);
  553. }
  554. ASSERT(LIST_EMPTY(&(Device->ArbiterListHead)) != FALSE);
  555. ASSERT(LIST_EMPTY(&(Device->ArbiterAllocationListHead)) != FALSE);
  556. return;
  557. }
  558. //
  559. // --------------------------------------------------------- Internal Functions
  560. //
  561. KSTATUS
  562. IopFinalizeResourceAllocation (
  563. PDEVICE Device
  564. )
  565. /*++
  566. Routine Description:
  567. This routine cements the resources allocated to a device in preparation for
  568. starting the device. Once this operation is complete, the device will have
  569. to be paused to rip up or move its resource allocations.
  570. Arguments:
  571. Device - Supplies a pointer to the device that is about to be started.
  572. Return Value:
  573. Status code.
  574. --*/
  575. {
  576. RESOURCE_ALLOCATION Allocation;
  577. PRESOURCE_ALLOCATION_LIST AllocationList;
  578. PARBITER_ENTRY ArbiterEntry;
  579. ULONG ArbiterEntryIndex;
  580. PLIST_ENTRY CurrentAllocation;
  581. PLIST_ENTRY CurrentEntry;
  582. PLIST_ENTRY CurrentRelatedEntry;
  583. PRESOURCE_ALLOCATION DependentAllocation;
  584. PARBITER_ENTRY DependentEntry;
  585. ULONG DependentEntryIndex;
  586. ULONG Index;
  587. PRESOURCE_ALLOCATION OwningAllocation;
  588. PRESOURCE_ALLOCATION_LIST ProcessorLocalResources;
  589. ULONG RequirementCount;
  590. KSTATUS Status;
  591. AllocationList = NULL;
  592. ProcessorLocalResources = NULL;
  593. //
  594. // If the device didn't ask for resources, then life is easy.
  595. //
  596. if (Device->SelectedConfiguration == NULL) {
  597. Status = STATUS_SUCCESS;
  598. goto FinalizeResourceAllocationEnd;
  599. }
  600. //
  601. // Rearrange the arbiter allocations to match the order of the resource
  602. // requirements.
  603. //
  604. IopArbiterMatchAllocationsToRequirements(Device, &RequirementCount);
  605. if (RequirementCount == 0) {
  606. Status = STATUS_SUCCESS;
  607. goto FinalizeResourceAllocationEnd;
  608. }
  609. //
  610. // Create the resource allocation buffer, which will hold the array of
  611. // resource allocations.
  612. //
  613. AllocationList = IoCreateResourceAllocationList();
  614. if (AllocationList == NULL) {
  615. Status = STATUS_INSUFFICIENT_RESOURCES;
  616. goto FinalizeResourceAllocationEnd;
  617. }
  618. RtlZeroMemory(&Allocation, sizeof(RESOURCE_ALLOCATION));
  619. //
  620. // Loop through the arbiter entry list and convert each entry to a resource
  621. // allocation.
  622. //
  623. CurrentEntry = Device->ArbiterAllocationListHead.Next;
  624. while (CurrentEntry != &(Device->ArbiterAllocationListHead)) {
  625. ArbiterEntry = LIST_VALUE(CurrentEntry,
  626. ARBITER_ENTRY,
  627. ConfigurationListEntry);
  628. CurrentEntry = CurrentEntry->Next;
  629. //
  630. // Initialize the resource allocation based on the arbiter entry, and
  631. // insert it onto the back of the list (maintains the same order).
  632. //
  633. IopArbiterInitializeResourceAllocation(ArbiterEntry, &Allocation);
  634. Status = IoCreateAndAddResourceAllocation(&Allocation, AllocationList);
  635. if (!KSUCCESS(Status)) {
  636. goto FinalizeResourceAllocationEnd;
  637. }
  638. //
  639. // Also at this time mark the arbiter entry as permanent.
  640. //
  641. ArbiterEntry->Type = ArbiterSpaceAllocated;
  642. }
  643. //
  644. // Copy and translate the bus local resources into processor local
  645. // resources.
  646. //
  647. Status = IopArbiterCopyAndTranslateResources(AllocationList,
  648. &ProcessorLocalResources);
  649. if (!KSUCCESS(Status)) {
  650. goto FinalizeResourceAllocationEnd;
  651. }
  652. //
  653. // Finish up by patching both the allocated bus and processor resources to
  654. // refer to any owning entries. The relationship goes in the reverse
  655. // direction of the arbiter relationship (i.e. the same direction as
  656. // related requirements).
  657. //
  658. ArbiterEntryIndex = 0;
  659. CurrentEntry = Device->ArbiterAllocationListHead.Next;
  660. while (CurrentEntry != &(Device->ArbiterAllocationListHead)) {
  661. ArbiterEntry = LIST_VALUE(CurrentEntry,
  662. ARBITER_ENTRY,
  663. ConfigurationListEntry);
  664. CurrentEntry = CurrentEntry->Next;
  665. //
  666. // Skip arbiter entries that have no dependent entries.
  667. //
  668. if (ArbiterEntry->DependentEntry == NULL) {
  669. ArbiterEntryIndex += 1;
  670. continue;
  671. }
  672. //
  673. // Find the index of the dependent entry.
  674. //
  675. DependentEntryIndex = 0;
  676. CurrentRelatedEntry = Device->ArbiterAllocationListHead.Next;
  677. while (CurrentRelatedEntry != &(Device->ArbiterAllocationListHead)) {
  678. DependentEntry = LIST_VALUE(CurrentRelatedEntry,
  679. ARBITER_ENTRY,
  680. ConfigurationListEntry);
  681. if (ArbiterEntry->DependentEntry == DependentEntry) {
  682. break;
  683. }
  684. CurrentRelatedEntry = CurrentRelatedEntry->Next;
  685. DependentEntryIndex += 1;
  686. }
  687. //
  688. // The dependent entry isn't in the list of allocated arbiter entries
  689. // for this device. It is likely that the dependent entry was for an
  690. // alternate requirement for this device. Or that a different device
  691. // sharing the resource filled in the dependent entry just in case this
  692. // device was going to allocate a similarly dependent resource. NULL it
  693. // out.
  694. //
  695. if (CurrentRelatedEntry == &(Device->ArbiterAllocationListHead)) {
  696. ArbiterEntry->DependentEntry = NULL;
  697. ArbiterEntryIndex += 1;
  698. continue;
  699. }
  700. //
  701. // Find the bus and processor allocations for the arbiter entry and
  702. // dependent entry. If both are found (and they should be), then link
  703. // the dependent entry's allocation back to the owning arbiter entry's
  704. // allocation.
  705. //
  706. Index = 0;
  707. OwningAllocation = NULL;
  708. DependentAllocation = NULL;
  709. CurrentAllocation = AllocationList->AllocationListHead.Next;
  710. while (CurrentAllocation != &(AllocationList->AllocationListHead)) {
  711. if (Index == ArbiterEntryIndex) {
  712. OwningAllocation = LIST_VALUE(CurrentAllocation,
  713. RESOURCE_ALLOCATION,
  714. ListEntry);
  715. }
  716. if (Index == DependentEntryIndex) {
  717. DependentAllocation = LIST_VALUE(CurrentAllocation,
  718. RESOURCE_ALLOCATION,
  719. ListEntry);
  720. }
  721. if ((OwningAllocation != NULL) && (DependentAllocation != NULL)) {
  722. DependentAllocation->OwningAllocation = OwningAllocation;
  723. break;
  724. }
  725. CurrentAllocation = CurrentAllocation->Next;
  726. Index += 1;
  727. }
  728. Index = 0;
  729. OwningAllocation = NULL;
  730. DependentAllocation = NULL;
  731. CurrentAllocation = ProcessorLocalResources->AllocationListHead.Next;
  732. while (CurrentAllocation !=
  733. &(ProcessorLocalResources->AllocationListHead)) {
  734. if (Index == ArbiterEntryIndex) {
  735. OwningAllocation = LIST_VALUE(CurrentAllocation,
  736. RESOURCE_ALLOCATION,
  737. ListEntry);
  738. }
  739. if (Index == DependentEntryIndex) {
  740. DependentAllocation = LIST_VALUE(CurrentAllocation,
  741. RESOURCE_ALLOCATION,
  742. ListEntry);
  743. }
  744. if ((OwningAllocation != NULL) && (DependentAllocation != NULL)) {
  745. DependentAllocation->OwningAllocation = OwningAllocation;
  746. break;
  747. }
  748. CurrentAllocation = CurrentAllocation->Next;
  749. Index += 1;
  750. }
  751. ArbiterEntryIndex += 1;
  752. }
  753. Status = STATUS_SUCCESS;
  754. FinalizeResourceAllocationEnd:
  755. if (!KSUCCESS(Status)) {
  756. if (AllocationList != NULL) {
  757. IoDestroyResourceAllocationList(AllocationList);
  758. AllocationList = NULL;
  759. }
  760. if (ProcessorLocalResources != NULL) {
  761. IoDestroyResourceAllocationList(ProcessorLocalResources);
  762. ProcessorLocalResources = NULL;
  763. }
  764. }
  765. Device->BusLocalResources = AllocationList;
  766. Device->ProcessorLocalResources = ProcessorLocalResources;
  767. return Status;
  768. }
  769. KSTATUS
  770. IopArbiterAddFreeSpace (
  771. PRESOURCE_ARBITER Arbiter,
  772. ULONGLONG FreeSpaceBegin,
  773. ULONGLONG FreeSpaceLength,
  774. ULONGLONG FreeSpaceCharacteristics,
  775. PRESOURCE_ALLOCATION SourcingAllocation,
  776. ULONGLONG TranslationOffset
  777. )
  778. /*++
  779. Routine Description:
  780. This routine adds a range of free space to the arbiter, allowing it to dole
  781. out these resources to child devices.
  782. Arguments:
  783. Arbiter - Supplies a pointer to the arbiter to add the resources to.
  784. FreeSpaceBegin - Supplies the beginning value of the free range.
  785. FreeSpaceLength - Supplies the length of the free space.
  786. FreeSpaceCharacteristics - Supplies the characteristics of this new free
  787. space.
  788. SourcingAllocation - Supplies a pointer to the parent resource allocation
  789. that makes this range possible. This pointer is optional. Supplying
  790. NULL here implies that the given resource is fixed in nature and
  791. cannot be expanded.
  792. TranslationOffset - Supplies the offset that has to be added to all
  793. doled out allocations on the secondary side to get an address in the
  794. source allocation space (primary side).
  795. To recap: SecondaryAddress + TranslationOffset = PrimaryAddress, where
  796. PrimaryAddress is closer to the CPU complex.
  797. Return Value:
  798. Status code.
  799. --*/
  800. {
  801. PLIST_ENTRY CurrentEntry;
  802. PARBITER_ENTRY ExistingEntry;
  803. PARBITER_ENTRY NewEntry;
  804. PARBITER_ENTRY PreviousEntry;
  805. KSTATUS Status;
  806. //
  807. // Allocate that new entry.
  808. //
  809. NewEntry = MmAllocatePagedPool(sizeof(ARBITER_ENTRY),
  810. ARBITER_ALLOCATION_TAG);
  811. if (NewEntry == NULL) {
  812. Status = STATUS_INSUFFICIENT_RESOURCES;
  813. goto ArbiterAddFreeSpaceEnd;
  814. }
  815. RtlZeroMemory(NewEntry, sizeof(ARBITER_ENTRY));
  816. NewEntry->Type = ArbiterSpaceFree;
  817. NewEntry->Allocation = FreeSpaceBegin;
  818. NewEntry->Length = FreeSpaceLength;
  819. NewEntry->Characteristics = FreeSpaceCharacteristics;
  820. NewEntry->FreeCharacteristics = FreeSpaceCharacteristics;
  821. NewEntry->SourceAllocation = SourcingAllocation;
  822. NewEntry->TranslationOffset = TranslationOffset;
  823. //
  824. // Find the proper place for this entry in the list.
  825. //
  826. ExistingEntry = NULL;
  827. CurrentEntry = Arbiter->EntryListHead.Next;
  828. while (CurrentEntry != &(Arbiter->EntryListHead)) {
  829. ExistingEntry = LIST_VALUE(CurrentEntry, ARBITER_ENTRY, ListEntry);
  830. if (ExistingEntry->Allocation >= NewEntry->Allocation) {
  831. break;
  832. }
  833. CurrentEntry = CurrentEntry->Next;
  834. }
  835. //
  836. // Check for overlaps.
  837. //
  838. if (CurrentEntry == &(Arbiter->EntryListHead)) {
  839. INSERT_BEFORE(&(NewEntry->ListEntry), &(Arbiter->EntryListHead));
  840. } else {
  841. //
  842. // Check to see if this should be merged with the previous entry. If so,
  843. // free the previous entry and expand this new one to cover it.
  844. //
  845. if (ExistingEntry->ListEntry.Previous != &(Arbiter->EntryListHead)) {
  846. PreviousEntry = LIST_VALUE(ExistingEntry->ListEntry.Previous,
  847. ARBITER_ENTRY,
  848. ListEntry);
  849. if ((PreviousEntry->Type == ArbiterSpaceFree) &&
  850. (PreviousEntry->Characteristics == NewEntry->Characteristics) &&
  851. (PreviousEntry->SourceAllocation ==
  852. NewEntry->SourceAllocation) &&
  853. (PreviousEntry->TranslationOffset ==
  854. NewEntry->TranslationOffset) &&
  855. (PreviousEntry->Allocation + PreviousEntry->Length >=
  856. NewEntry->Allocation)) {
  857. NewEntry->Length += NewEntry->Allocation -
  858. PreviousEntry->Allocation;
  859. if (PreviousEntry->Length > NewEntry->Length) {
  860. NewEntry->Length = PreviousEntry->Length;
  861. }
  862. NewEntry->Allocation = PreviousEntry->Allocation;
  863. LIST_REMOVE(&(PreviousEntry->ListEntry));
  864. ASSERT(PreviousEntry->ConfigurationListEntry.Next == NULL);
  865. MmFreePagedPool(PreviousEntry);
  866. }
  867. }
  868. //
  869. // Check to see if this should be merged with the next entry. If so,
  870. // free up the new entry and expand the existing one to cover it.
  871. //
  872. if ((ExistingEntry->Type == ArbiterSpaceFree) &&
  873. (ExistingEntry->Characteristics == NewEntry->Characteristics) &&
  874. (ExistingEntry->SourceAllocation == NewEntry->SourceAllocation) &&
  875. (ExistingEntry->TranslationOffset == NewEntry->TranslationOffset) &&
  876. (NewEntry->Allocation + NewEntry->Length >=
  877. ExistingEntry->Allocation)) {
  878. ExistingEntry->Length += ExistingEntry->Allocation -
  879. NewEntry->Allocation;
  880. if (NewEntry->Length > ExistingEntry->Length) {
  881. ExistingEntry->Length = NewEntry->Length;
  882. }
  883. ExistingEntry->Allocation = NewEntry->Allocation;
  884. MmFreePagedPool(NewEntry);
  885. NewEntry = NULL;
  886. }
  887. //
  888. // If the new entry is still around, add it to the list before the
  889. // existing one.
  890. //
  891. if (NewEntry != NULL) {
  892. //
  893. // Check to see if it should be shrunk.
  894. //
  895. if (NewEntry->Allocation + NewEntry->Length >
  896. ExistingEntry->Allocation) {
  897. NewEntry->Length = ExistingEntry->Allocation -
  898. NewEntry->Allocation;
  899. ASSERT(NewEntry->Length != 0);
  900. }
  901. INSERT_BEFORE(&(NewEntry->ListEntry), CurrentEntry);
  902. }
  903. }
  904. Status = STATUS_SUCCESS;
  905. ArbiterAddFreeSpaceEnd:
  906. return Status;
  907. }
  908. KSTATUS
  909. IopArbiterAllocateSpace (
  910. PARBITER_ALLOCATION_CONTEXT Context,
  911. UINTN RequirementIndex,
  912. PRESOURCE_REQUIREMENT Alternative
  913. )
  914. /*++
  915. Routine Description:
  916. This routine attempts to allocate space from an arbiter.
  917. Arguments:
  918. Context - Supplies a pointer to the arbiter allocation context.
  919. RequirementIndex - Supplies the index of the requirement. If an alternative
  920. requirement is provided, then the routine will attempt to satisfy said
  921. alternative, but will set the corresponding requirement field of the
  922. arbiter entry to that of the requirement index. Thus, the allocation
  923. always points at the first requirement, not the potentially alternative
  924. requirement being satisfied.
  925. Alternative - Supplies an optional pointer to an alternative resource
  926. requirement to satisfy.
  927. Return Value:
  928. Status code.
  929. --*/
  930. {
  931. ULONGLONG AllocationEnd;
  932. BOOL AllowOverlaps;
  933. PRESOURCE_ARBITER Arbiter;
  934. PARBITER_ENTRY ArbiterEntry;
  935. PARBITER_ENTRY CompatibleSpace;
  936. PLIST_ENTRY CurrentEntry;
  937. PDEVICE Device;
  938. ULONG Index;
  939. PARBITER_ENTRY NewAllocation;
  940. PARBITER_ENTRY OwningRequirementEntry;
  941. ULONGLONG PotentialAllocation;
  942. PARBITER_ENTRY RequiredSpace;
  943. PRESOURCE_REQUIREMENT Requirement;
  944. PARBITER_ALLOCATION_REQUIREMENT RequirementData;
  945. PRESOURCE_REQUIREMENT RootRequirement;
  946. KSTATUS Status;
  947. NewAllocation = NULL;
  948. //
  949. // If an alternative requirement was supplied, then use it.
  950. //
  951. RootRequirement = Context->Requirements[RequirementIndex].Requirement;
  952. if (Alternative != NULL) {
  953. ASSERT(Alternative->Type == RootRequirement->Type);
  954. Requirement = Alternative;
  955. } else {
  956. Requirement = RootRequirement;
  957. }
  958. RequirementData = &(Context->Requirements[RequirementIndex]);
  959. Device = IOP_ARBITER_GET_DEVICE(Context, RequirementData);
  960. Arbiter = IOP_ARBITER_GET_ARBITER(Context, RequirementData);
  961. ASSERT(Arbiter != NULL);
  962. //
  963. // If this requirement has a owning requirement, then search for the
  964. // allocated arbiter entry associated with it.
  965. //
  966. OwningRequirementEntry = NULL;
  967. if (Requirement->OwningRequirement != NULL) {
  968. for (Index = 0; Index < Context->RequirementCount; Index += 1) {
  969. ArbiterEntry = Context->Requirements[Index].Allocation;
  970. if ((ArbiterEntry != NULL) &&
  971. (ArbiterEntry->CorrespondingRequirement ==
  972. Requirement->OwningRequirement)) {
  973. OwningRequirementEntry = ArbiterEntry;
  974. break;
  975. }
  976. }
  977. //
  978. // If the owning requirement has an allocated arbiter entry and that
  979. // arbiter entry has a dependent arbiter allocation, then this
  980. // requirement needs to use those exact resources. The owning arbiter
  981. // entry picked up the dependent entry from another device's use of the
  982. // same region.
  983. //
  984. if ((OwningRequirementEntry != NULL) &&
  985. (OwningRequirementEntry->DependentEntry != NULL)) {
  986. RequiredSpace = OwningRequirementEntry->DependentEntry;
  987. ASSERT(RequiredSpace->Type != ArbiterSpaceFree);
  988. ASSERT(RequiredSpace->CorrespondingRequirement->Type ==
  989. Requirement->Type);
  990. //
  991. // If the space does not match the requirement, then it cannot be
  992. // used and something is wrong.
  993. //
  994. if ((RequiredSpace->Characteristics !=
  995. Requirement->Characteristics) ||
  996. ((Requirement->Flags & RESOURCE_FLAG_NOT_SHAREABLE) != 0) ||
  997. ((RequiredSpace->Flags & RESOURCE_FLAG_NOT_SHAREABLE) != 0) ||
  998. (Requirement->Length != RequiredSpace->Length)) {
  999. Status = STATUS_RESOURCE_IN_USE;
  1000. goto ArbiterAllocateSpaceEnd;
  1001. }
  1002. //
  1003. // The required allocation must have the correct alignment.
  1004. //
  1005. if (IS_ALIGNED(RequiredSpace->Allocation,
  1006. Requirement->Alignment) == FALSE) {
  1007. Status = STATUS_RESOURCE_IN_USE;
  1008. goto ArbiterAllocateSpaceEnd;
  1009. }
  1010. //
  1011. // The allocation must also fit within the required bounds.
  1012. //
  1013. PotentialAllocation = RequiredSpace->Allocation;
  1014. AllocationEnd = PotentialAllocation + Requirement->Length;
  1015. if ((PotentialAllocation < Requirement->Minimum) ||
  1016. (AllocationEnd > Requirement->Maximum)) {
  1017. Status = STATUS_RESOURCE_IN_USE;
  1018. goto ArbiterAllocateSpaceEnd;
  1019. }
  1020. //
  1021. // The required space works! Create a new arbiter entry.
  1022. //
  1023. Status = IopArbiterInsertEntry(Arbiter,
  1024. ArbiterSpaceReserved,
  1025. Device,
  1026. PotentialAllocation,
  1027. Requirement->Length,
  1028. Requirement->Characteristics,
  1029. Requirement->Flags,
  1030. RootRequirement,
  1031. RequiredSpace,
  1032. &NewAllocation);
  1033. goto ArbiterAllocateSpaceEnd;
  1034. }
  1035. }
  1036. //
  1037. // Zero-length requirements have no issue with overlap. Just allocate an
  1038. // arbiter entry.
  1039. //
  1040. if (Requirement->Length == 0) {
  1041. Status = IopArbiterInsertEntry(Arbiter,
  1042. ArbiterSpaceReserved,
  1043. Device,
  1044. Requirement->Minimum,
  1045. 0,
  1046. Requirement->Characteristics,
  1047. Requirement->Flags,
  1048. RootRequirement,
  1049. NULL,
  1050. &NewAllocation);
  1051. goto ArbiterAllocateSpaceEnd;
  1052. }
  1053. //
  1054. // Loop through every entry in the arbiter twice, first looking for only
  1055. // free space and then allowing overlaps.
  1056. //
  1057. AllowOverlaps = FALSE;
  1058. while (TRUE) {
  1059. CurrentEntry = Arbiter->EntryListHead.Next;
  1060. while (CurrentEntry != &(Arbiter->EntryListHead)) {
  1061. CompatibleSpace = LIST_VALUE(CurrentEntry,
  1062. ARBITER_ENTRY,
  1063. ListEntry);
  1064. CurrentEntry = CurrentEntry->Next;
  1065. //
  1066. // If the entry isn't free, then it probably won't work. The only
  1067. // supported overlaps are two entries that both satisfy the given
  1068. // criteria:
  1069. //
  1070. // 1) Same characteristics.
  1071. // 2) Same base works for both.
  1072. // 3) Same length.
  1073. //
  1074. if (CompatibleSpace->Type != ArbiterSpaceFree) {
  1075. if (AllowOverlaps == FALSE) {
  1076. continue;
  1077. }
  1078. if ((CompatibleSpace->Length != Requirement->Length) ||
  1079. (CompatibleSpace->Characteristics !=
  1080. Requirement->Characteristics) ||
  1081. ((Requirement->Flags & RESOURCE_FLAG_NOT_SHAREABLE) != 0) ||
  1082. ((CompatibleSpace->Flags & RESOURCE_FLAG_NOT_SHAREABLE) !=
  1083. 0)) {
  1084. continue;
  1085. }
  1086. if (IS_ALIGNED(CompatibleSpace->Allocation,
  1087. Requirement->Alignment) == FALSE) {
  1088. continue;
  1089. }
  1090. }
  1091. //
  1092. // Skip it if it's below the minimum.
  1093. //
  1094. if ((CompatibleSpace->Allocation + CompatibleSpace->Length) <=
  1095. Requirement->Minimum) {
  1096. continue;
  1097. }
  1098. //
  1099. // If characteristics are set in the free space, then those
  1100. // characteristics are assumed to be serious and need to be matched.
  1101. //
  1102. if ((CompatibleSpace->Characteristics &
  1103. Requirement->Characteristics) !=
  1104. CompatibleSpace->Characteristics) {
  1105. continue;
  1106. }
  1107. //
  1108. // Attempt to fit an allocation in here.
  1109. //
  1110. if (CompatibleSpace->Allocation > Requirement->Minimum) {
  1111. PotentialAllocation = CompatibleSpace->Allocation;
  1112. } else {
  1113. PotentialAllocation = Requirement->Minimum;
  1114. }
  1115. PotentialAllocation = ALIGN_RANGE_UP(PotentialAllocation,
  1116. Requirement->Alignment);
  1117. //
  1118. // If this is not a free entry, the allocations had better be equal
  1119. // (or else releasing the allocation won't work properly.
  1120. //
  1121. ASSERT((CompatibleSpace->Type == ArbiterSpaceFree) ||
  1122. (PotentialAllocation == CompatibleSpace->Allocation));
  1123. AllocationEnd = PotentialAllocation + Requirement->Length;
  1124. //
  1125. // If the end here is beyond the maximum, then no allocation in the
  1126. // arbiter will work.
  1127. //
  1128. if (AllocationEnd > Requirement->Maximum) {
  1129. Status = STATUS_UNSUCCESSFUL;
  1130. goto ArbiterAllocateSpaceEnd;
  1131. }
  1132. //
  1133. // If the allocation doesn't fit, move on to the next arbiter entry.
  1134. //
  1135. if (AllocationEnd >
  1136. (CompatibleSpace->Allocation + CompatibleSpace->Length)) {
  1137. continue;
  1138. }
  1139. //
  1140. // The allocation fits! Create a new arbiter entry.
  1141. //
  1142. Status = IopArbiterInsertEntry(Arbiter,
  1143. ArbiterSpaceReserved,
  1144. Device,
  1145. PotentialAllocation,
  1146. Requirement->Length,
  1147. Requirement->Characteristics,
  1148. Requirement->Flags,
  1149. RootRequirement,
  1150. CompatibleSpace,
  1151. &NewAllocation);
  1152. goto ArbiterAllocateSpaceEnd;
  1153. }
  1154. //
  1155. // If the list has already been searched allowing overlaps, then it's
  1156. // time to bail out. No arbiter space was found to be satisfactory.
  1157. //
  1158. if (AllowOverlaps != FALSE) {
  1159. break;
  1160. }
  1161. //
  1162. // Next time around, allow this allocation to overlap with existing
  1163. // resources.
  1164. //
  1165. AllowOverlaps = TRUE;
  1166. }
  1167. Status = STATUS_RESOURCE_IN_USE;
  1168. ArbiterAllocateSpaceEnd:
  1169. if (KSUCCESS(Status)) {
  1170. if (OwningRequirementEntry != NULL) {
  1171. OwningRequirementEntry->DependentEntry = NewAllocation;
  1172. }
  1173. Context->Requirements[RequirementIndex].Allocation = NewAllocation;
  1174. }
  1175. return Status;
  1176. }
  1177. KSTATUS
  1178. IopArbiterInsertEntry (
  1179. PRESOURCE_ARBITER Arbiter,
  1180. ARBITER_SPACE_TYPE SpaceType,
  1181. PDEVICE ClaimingDevice,
  1182. ULONGLONG Allocation,
  1183. ULONGLONG Length,
  1184. ULONGLONG Characteristics,
  1185. ULONG Flags,
  1186. PRESOURCE_REQUIREMENT RootRequirement,
  1187. PARBITER_ENTRY ExistingEntry,
  1188. PARBITER_ENTRY *NewEntry
  1189. )
  1190. /*++
  1191. Routine Description:
  1192. This routine inserts an entry into the arbiter. It does not perform any
  1193. checks for resource conflicts, so it is only for use by the arbiter. An
  1194. external function would want to do much more involved conflict checking.
  1195. Arguments:
  1196. Arbiter - Supplies a pointer to the arbiter to add the new entry to.
  1197. SpaceType - Supplies the type of arbiter space this entry should be set
  1198. to.
  1199. ClaimingDevice - Supplies a pointer to the device that will be using this
  1200. region.
  1201. Allocation - Supplies the allocation base.
  1202. Length - Supplies the length of the allocation.
  1203. Characteristics - Supplies the allocation characteristics.
  1204. Flags - Supplies the flags for the allocation.
  1205. RootRequirement - Supplies the requirment to set as the "corresponding
  1206. requirement" of this arbiter entry, used to connect arbiter allocations
  1207. with resource requirements.
  1208. ExistingEntry - Supplies an optional pointer to the entry that currently
  1209. exists for the range that is to be given to the new entry. This may be
  1210. a free entry or an allocated, yet shareable, entry.
  1211. NewEntry - Supplies a pointer where a pointer to the new entry will be
  1212. returned. This memory is managed by the arbiter.
  1213. Return Value:
  1214. Status code.
  1215. --*/
  1216. {
  1217. ULONGLONG AllocationEnd;
  1218. PLIST_ENTRY CurrentEntry;
  1219. PARBITER_ENTRY Leftovers;
  1220. PARBITER_ENTRY NewAllocation;
  1221. PARBITER_ENTRY NextEntry;
  1222. KSTATUS Status;
  1223. AllocationEnd = Allocation + Length;
  1224. //
  1225. // Create and initialize a new arbiter entry.
  1226. //
  1227. NewAllocation = MmAllocatePagedPool(sizeof(ARBITER_ENTRY),
  1228. ARBITER_ALLOCATION_TAG);
  1229. if (NewAllocation == NULL) {
  1230. Status = STATUS_INSUFFICIENT_RESOURCES;
  1231. goto ArbiterInsertEntryEnd;
  1232. }
  1233. RtlZeroMemory(NewAllocation, sizeof(ARBITER_ENTRY));
  1234. NewAllocation->Type = ArbiterSpaceReserved;
  1235. NewAllocation->Device = ClaimingDevice;
  1236. NewAllocation->Allocation = Allocation;
  1237. NewAllocation->Length = Length;
  1238. NewAllocation->Characteristics = Characteristics;
  1239. NewAllocation->Flags = Flags;
  1240. NewAllocation->CorrespondingRequirement = RootRequirement;
  1241. if (ExistingEntry != NULL) {
  1242. NewAllocation->FreeCharacteristics = ExistingEntry->FreeCharacteristics;
  1243. NewAllocation->SourceAllocation = ExistingEntry->SourceAllocation;
  1244. NewAllocation->TranslationOffset = ExistingEntry->TranslationOffset;
  1245. ASSERT((ExistingEntry->Type != ArbiterSpaceFree) ||
  1246. (ExistingEntry->DependentEntry == NULL));
  1247. NewAllocation->DependentEntry = ExistingEntry->DependentEntry;
  1248. }
  1249. if (ExistingEntry != NULL) {
  1250. //
  1251. // If there is leftover space, allocate an entry for that.
  1252. //
  1253. if ((ExistingEntry->Type == ArbiterSpaceFree) &&
  1254. (AllocationEnd <
  1255. (ExistingEntry->Allocation + ExistingEntry->Length))) {
  1256. Leftovers = MmAllocatePagedPool(sizeof(ARBITER_ENTRY),
  1257. ARBITER_ALLOCATION_TAG);
  1258. if (Leftovers == NULL) {
  1259. Status = STATUS_INSUFFICIENT_RESOURCES;
  1260. goto ArbiterInsertEntryEnd;
  1261. }
  1262. RtlCopyMemory(Leftovers, ExistingEntry, sizeof(ARBITER_ENTRY));
  1263. Leftovers->Allocation = AllocationEnd;
  1264. Leftovers->Length = ExistingEntry->Allocation +
  1265. ExistingEntry->Length -
  1266. AllocationEnd;
  1267. INSERT_AFTER(&(Leftovers->ListEntry), &(ExistingEntry->ListEntry));
  1268. }
  1269. INSERT_AFTER(&(NewAllocation->ListEntry), &(ExistingEntry->ListEntry));
  1270. //
  1271. // Shrink the old free entry, and remove it if it shrinks all the way
  1272. // to zero.
  1273. //
  1274. if (ExistingEntry->Type == ArbiterSpaceFree) {
  1275. ExistingEntry->Length = Allocation - ExistingEntry->Allocation;
  1276. if (ExistingEntry->Length == 0) {
  1277. LIST_REMOVE(&(ExistingEntry->ListEntry));
  1278. MmFreePagedPool(ExistingEntry);
  1279. }
  1280. }
  1281. //
  1282. // Find the right spot to insert this new entry.
  1283. //
  1284. } else {
  1285. CurrentEntry = Arbiter->EntryListHead.Next;
  1286. while (CurrentEntry != &(Arbiter->EntryListHead)) {
  1287. NextEntry = LIST_VALUE(CurrentEntry, ARBITER_ENTRY, ListEntry);
  1288. if (NextEntry->Allocation >= Allocation) {
  1289. break;
  1290. }
  1291. CurrentEntry = CurrentEntry->Next;
  1292. }
  1293. if (CurrentEntry == &(Arbiter->EntryListHead)) {
  1294. INSERT_BEFORE(&(NewAllocation->ListEntry),
  1295. &(Arbiter->EntryListHead));
  1296. } else {
  1297. INSERT_BEFORE(&(NewAllocation->ListEntry), &(NextEntry->ListEntry));
  1298. }
  1299. }
  1300. Status = STATUS_SUCCESS;
  1301. ArbiterInsertEntryEnd:
  1302. if (!KSUCCESS(Status)) {
  1303. if (NewAllocation != NULL) {
  1304. MmFreePagedPool(NewAllocation);
  1305. NewAllocation = NULL;
  1306. }
  1307. }
  1308. *NewEntry = NewAllocation;
  1309. return Status;
  1310. }
  1311. VOID
  1312. IopArbiterFreeEntry (
  1313. PRESOURCE_ARBITER Arbiter,
  1314. PARBITER_ENTRY Entry
  1315. )
  1316. /*++
  1317. Routine Description:
  1318. This routine frees an arbiter entry.
  1319. Arguments:
  1320. Arbiter - Supplies a pointer to the arbiter where the allocation belongs.
  1321. Entry - Supplies a pointer to the arbiter allocation.
  1322. Return Value:
  1323. Status code.
  1324. --*/
  1325. {
  1326. ULONGLONG AllocationBegin;
  1327. ULONGLONG Characteristics;
  1328. PARBITER_ENTRY NextEntry;
  1329. PARBITER_ENTRY OverlappingEntry;
  1330. PARBITER_ENTRY PreviousEntry;
  1331. ASSERT(Entry->Type != ArbiterSpaceFree);
  1332. AllocationBegin = Entry->Allocation;
  1333. Characteristics = Entry->FreeCharacteristics;
  1334. PreviousEntry = LIST_VALUE(Entry->ListEntry.Previous,
  1335. ARBITER_ENTRY,
  1336. ListEntry);
  1337. NextEntry = LIST_VALUE(Entry->ListEntry.Next, ARBITER_ENTRY, ListEntry);
  1338. LIST_REMOVE(&(Entry->ListEntry));
  1339. if (Entry->Length == 0) {
  1340. return;
  1341. }
  1342. //
  1343. // Attempt to find an entry that overlapped with this one. If such an entry
  1344. // exists, don't patch up free space into this region, since some other
  1345. // allocation is still there. Just make this allocation disappear.
  1346. //
  1347. OverlappingEntry = IopArbiterFindEntry(Arbiter, AllocationBegin, FALSE);
  1348. if (OverlappingEntry != NULL) {
  1349. ASSERT(OverlappingEntry->Type != ArbiterSpaceFree);
  1350. MmFreePagedPool(Entry);
  1351. return;
  1352. }
  1353. //
  1354. // Put the entry back on the list, as it makes it easier for the
  1355. // coalescing code.
  1356. //
  1357. INSERT_AFTER(&(Entry->ListEntry), &(PreviousEntry->ListEntry));
  1358. //
  1359. // If the previous entry is free and comes up to meet this allocation, then
  1360. // expand that allocation. Remove and free this allocation.
  1361. //
  1362. if ((Entry->ListEntry.Previous != &(Arbiter->EntryListHead)) &&
  1363. (PreviousEntry->Type == ArbiterSpaceFree) &&
  1364. (PreviousEntry->SourceAllocation == Entry->SourceAllocation) &&
  1365. (PreviousEntry->TranslationOffset == Entry->TranslationOffset) &&
  1366. (PreviousEntry->Characteristics == Characteristics) &&
  1367. (PreviousEntry->Allocation + PreviousEntry->Length ==
  1368. Entry->Allocation)) {
  1369. PreviousEntry->Length += Entry->Length;
  1370. LIST_REMOVE(&(Entry->ListEntry));
  1371. MmFreePagedPool(Entry);
  1372. //
  1373. // Set the current entry to that previous entry that expanded out.
  1374. //
  1375. Entry = PreviousEntry;
  1376. }
  1377. //
  1378. // See if the next allocation can swallow up this one.
  1379. //
  1380. if ((Entry->ListEntry.Next != &(Arbiter->EntryListHead)) &&
  1381. (NextEntry->Type == ArbiterSpaceFree) &&
  1382. (NextEntry->SourceAllocation == Entry->SourceAllocation) &&
  1383. (NextEntry->TranslationOffset == Entry->TranslationOffset) &&
  1384. (NextEntry->Characteristics == Characteristics) &&
  1385. (Entry->Allocation + Entry->Length == NextEntry->Allocation)) {
  1386. NextEntry->Length += Entry->Length;
  1387. NextEntry->Allocation = Entry->Allocation;
  1388. LIST_REMOVE(&(Entry->ListEntry));
  1389. MmFreePagedPool(Entry);
  1390. Entry = NULL;
  1391. }
  1392. //
  1393. // If the entry is not already marked as free, mark it as such now.
  1394. //
  1395. if ((Entry != NULL) && (Entry->Type != ArbiterSpaceFree)) {
  1396. Entry->Device = NULL;
  1397. Entry->CorrespondingRequirement = NULL;
  1398. Entry->Characteristics = Characteristics;
  1399. Entry->Flags = 0;
  1400. Entry->Type = ArbiterSpaceFree;
  1401. Entry->DependentEntry = NULL;
  1402. }
  1403. return;
  1404. }
  1405. VOID
  1406. IopArbiterDestroy (
  1407. PRESOURCE_ARBITER Arbiter
  1408. )
  1409. /*++
  1410. Routine Description:
  1411. This routine destroys an individual resource arbiter, removing it from its
  1412. list of arbiters.
  1413. Arguments:
  1414. Arbiter - Supplies a pointer to the arbiter that is to be destroyed.
  1415. Return Value:
  1416. None.
  1417. --*/
  1418. {
  1419. PARBITER_ENTRY ArbiterEntry;
  1420. PLIST_ENTRY CurrentEntry;
  1421. //
  1422. // In the destruction path, there is no point to free any of the arbiter
  1423. // entries, just loop here and nuke them.
  1424. //
  1425. CurrentEntry = Arbiter->EntryListHead.Next;
  1426. while (CurrentEntry != &(Arbiter->EntryListHead)) {
  1427. ArbiterEntry = LIST_VALUE(CurrentEntry, ARBITER_ENTRY, ListEntry);
  1428. CurrentEntry = CurrentEntry->Next;
  1429. LIST_REMOVE(&(ArbiterEntry->ConfigurationListEntry));
  1430. LIST_REMOVE(&(ArbiterEntry->ListEntry));
  1431. MmFreePagedPool(ArbiterEntry);
  1432. }
  1433. //
  1434. // Destroy the arbiter itself.
  1435. //
  1436. LIST_REMOVE(&(Arbiter->ListEntry));
  1437. MmFreePagedPool(Arbiter);
  1438. return;
  1439. }
  1440. PRESOURCE_ARBITER
  1441. IopArbiterFindArbiter (
  1442. PDEVICE Device,
  1443. RESOURCE_TYPE ResourceType
  1444. )
  1445. /*++
  1446. Routine Description:
  1447. This routine searches for the arbiter of the given resouce type that is
  1448. attached to the given device.
  1449. Arguments:
  1450. Device - Supplies a pointer to the device whose arbiter list is to be
  1451. searched.
  1452. ResourceType - Supplies the resource type of the requested arbiter.
  1453. Return Value:
  1454. A pointer to a resource arbiter on success. NULL on failure.
  1455. --*/
  1456. {
  1457. PRESOURCE_ARBITER Arbiter;
  1458. PRESOURCE_ARBITER CurrentArbiter;
  1459. PLIST_ENTRY CurrentEntry;
  1460. //
  1461. // Find the arbiter with the provided resource type.
  1462. //
  1463. Arbiter = NULL;
  1464. CurrentEntry = Device->ArbiterListHead.Next;
  1465. while (CurrentEntry != &(Device->ArbiterListHead)) {
  1466. CurrentArbiter = LIST_VALUE(CurrentEntry, RESOURCE_ARBITER, ListEntry);
  1467. CurrentEntry = CurrentEntry->Next;
  1468. if (CurrentArbiter->ResourceType == ResourceType) {
  1469. Arbiter = CurrentArbiter;
  1470. break;
  1471. }
  1472. }
  1473. return Arbiter;
  1474. }
  1475. PARBITER_ENTRY
  1476. IopArbiterFindEntry (
  1477. PRESOURCE_ARBITER Arbiter,
  1478. ULONGLONG Allocation,
  1479. BOOL DependentEntryPreferred
  1480. )
  1481. /*++
  1482. Routine Description:
  1483. This routine attempts to find an arbiter entry for the given allocation.
  1484. If there are more than one arbiter entries covering the same range, this
  1485. routine will simply find the first one it comes across. If the dependent
  1486. entry parameter is set to TRUE, then it will find the first one with a
  1487. dependent entry filled in. If no such entry exists, then it will return the
  1488. first one.
  1489. Arguments:
  1490. Arbiter - Supplies a pointer to the arbiter to search.
  1491. Allocation - Supplies a pointer to the allocation value to check.
  1492. DependentEntryPreferred - Supplies a boolean indicating whether or not the
  1493. search should prioritize finding any entry that has a valid dependent
  1494. entry field.
  1495. Return Value:
  1496. Returns a pointer to the first arbiter entry that covers the given
  1497. allocation value.
  1498. NULL if no arbiter entry covers the given value.
  1499. --*/
  1500. {
  1501. PLIST_ENTRY CurrentEntry;
  1502. PARBITER_ENTRY Entry;
  1503. PARBITER_ENTRY FirstEntry;
  1504. FirstEntry = NULL;
  1505. CurrentEntry = Arbiter->EntryListHead.Next;
  1506. while (CurrentEntry != &(Arbiter->EntryListHead)) {
  1507. Entry = LIST_VALUE(CurrentEntry, ARBITER_ENTRY, ListEntry);
  1508. CurrentEntry = CurrentEntry->Next;
  1509. if ((Entry->Allocation <= Allocation) &&
  1510. (Entry->Allocation + Entry->Length > Allocation)) {
  1511. //
  1512. // Return this entry if it doesn't need to have a dependent entry
  1513. // or it has a dependent entry.
  1514. //
  1515. if ((DependentEntryPreferred == FALSE) ||
  1516. (Entry->DependentEntry != NULL)) {
  1517. return Entry;
  1518. }
  1519. if (FirstEntry == NULL) {
  1520. FirstEntry = Entry;
  1521. }
  1522. //
  1523. // If a non-satisfying entry was found after the satisfying entries
  1524. // have been checked, return the first entry found.
  1525. //
  1526. } else if (FirstEntry != NULL) {
  1527. break;
  1528. }
  1529. }
  1530. return FirstEntry;
  1531. }
  1532. VOID
  1533. IopArbiterAddRequirement (
  1534. PARBITER_ALLOCATION_CONTEXT Context,
  1535. PRESOURCE_REQUIREMENT Requirement,
  1536. PDEVICE Device
  1537. )
  1538. /*++
  1539. Routine Description:
  1540. This routine adds a requirement to the arbiter allocation context. The
  1541. caller must have previously called resize arbiter context so that the
  1542. arrays are large enough.
  1543. Arguments:
  1544. Context - Supplies a pointer to the initialized allocation context.
  1545. Requirement - Supplies a pointer to the requirement to add.
  1546. Device - Supplies a pointer to the device that generated the requirement.
  1547. Return Value:
  1548. None. An arbiter is always found since the root device has empty ones for
  1549. each type.
  1550. --*/
  1551. {
  1552. PRESOURCE_ARBITER Arbiter;
  1553. UINTN ArbiterIndex;
  1554. UINTN DeviceIndex;
  1555. ULONG EmptySlot;
  1556. PLIST_ENTRY FirstConfigurationListEntry;
  1557. PDEVICE Provider;
  1558. PARBITER_ALLOCATION_REQUIREMENT RequirementData;
  1559. ULONG RequirementIndex;
  1560. RequirementIndex = Context->RequirementCount;
  1561. RequirementData = &(Context->Requirements[RequirementIndex]);
  1562. RequirementData->Requirement = Requirement;
  1563. RequirementData->Allocation = NULL;
  1564. ASSERT((ARBITER_TYPE)Requirement->Type < ArbiterTypeCount);
  1565. //
  1566. // The arbiter comes from the device's parent unless a different provider
  1567. // was explicitly given.
  1568. //
  1569. Provider = Device->ParentDevice;
  1570. if (Requirement->Provider != NULL) {
  1571. Provider = Requirement->Provider;
  1572. }
  1573. //
  1574. // Walk up the chain of parents to find the arbiter for this requirement.
  1575. //
  1576. while (TRUE) {
  1577. Arbiter = IopArbiterFindArbiter(Provider, Requirement->Type);
  1578. //
  1579. // If an arbiter was found, see if it's already in the arbiter array.
  1580. // Insert if not, or just set the index if it is.
  1581. //
  1582. if (Arbiter != NULL) {
  1583. for (ArbiterIndex = 0;
  1584. ArbiterIndex < Context->ArbiterCount;
  1585. ArbiterIndex += 1) {
  1586. if (Context->ArbiterData[ArbiterIndex].Arbiter == Arbiter) {
  1587. break;
  1588. }
  1589. }
  1590. if (ArbiterIndex == Context->ArbiterCount) {
  1591. Context->ArbiterData[ArbiterIndex].Arbiter = Arbiter;
  1592. Context->ArbiterCount = ArbiterIndex + 1;
  1593. }
  1594. RequirementData->ArbiterIndex = ArbiterIndex;
  1595. break;
  1596. }
  1597. Provider = Provider->ParentDevice;
  1598. ASSERT(Provider != NULL);
  1599. }
  1600. //
  1601. // Also find the device index for this requirement, or add the device if
  1602. // it's new. Try to reuse empty slots from removed devices.
  1603. //
  1604. EmptySlot = Context->DeviceCount;
  1605. for (DeviceIndex = 0;
  1606. DeviceIndex < Context->DeviceCount;
  1607. DeviceIndex += 1) {
  1608. if (Context->Device[DeviceIndex] == Device) {
  1609. break;
  1610. }
  1611. if (Context->Device[DeviceIndex] == NULL) {
  1612. EmptySlot = DeviceIndex;
  1613. }
  1614. }
  1615. if (DeviceIndex == Context->DeviceCount) {
  1616. DeviceIndex = EmptySlot;
  1617. Context->Device[EmptySlot] = Device;
  1618. FirstConfigurationListEntry =
  1619. Device->ResourceRequirements->RequirementListListHead.Next;
  1620. Context->CurrentDeviceConfiguration[EmptySlot] =
  1621. LIST_VALUE(FirstConfigurationListEntry,
  1622. RESOURCE_REQUIREMENT_LIST,
  1623. ListEntry);
  1624. if (EmptySlot == Context->DeviceCount) {
  1625. Context->DeviceCount += 1;
  1626. }
  1627. }
  1628. RequirementData->DeviceIndex = DeviceIndex;
  1629. RequirementData->Allocation = NULL;
  1630. Context->RequirementCount += 1;
  1631. return;
  1632. }
  1633. KSTATUS
  1634. IopArbiterInitializeAllocationContext (
  1635. PDEVICE Device,
  1636. PARBITER_ALLOCATION_CONTEXT *NewContext
  1637. )
  1638. /*++
  1639. Routine Description:
  1640. This routine creates and initializes an arbiter allocation context, and
  1641. seeds it with the resource requirements for the most optimal configuration
  1642. for the given device.
  1643. Arguments:
  1644. Device - Supplies a pointer to the new kid on the block, the device trying
  1645. to get resources.
  1646. NewContext - Supplies a pointer that on success will receive a pointer to
  1647. the arbiter allocation context. The caller is responsible for
  1648. destroying this context.
  1649. Return Value:
  1650. Status code.
  1651. --*/
  1652. {
  1653. PARBITER_ALLOCATION_CONTEXT Context;
  1654. PLIST_ENTRY CurrentEntry;
  1655. PRESOURCE_REQUIREMENT_LIST FirstConfiguration;
  1656. PLIST_ENTRY FirstConfigurationListEntry;
  1657. PRESOURCE_REQUIREMENT Requirement;
  1658. ULONG RequirementCount;
  1659. KSTATUS Status;
  1660. //
  1661. // Create an arbiter allocation context.
  1662. //
  1663. Context = MmAllocatePagedPool(sizeof(ARBITER_ALLOCATION_CONTEXT),
  1664. ARBITER_ALLOCATION_TAG);
  1665. if (Context == NULL) {
  1666. Status = STATUS_INSUFFICIENT_RESOURCES;
  1667. goto ArbiterInitializeAllocationContextEnd;
  1668. }
  1669. RtlZeroMemory(Context, sizeof(ARBITER_ALLOCATION_CONTEXT));
  1670. if ((Device->ResourceRequirements == NULL) ||
  1671. (LIST_EMPTY(&(Device->ResourceRequirements->RequirementListListHead)) !=
  1672. FALSE)) {
  1673. Status = STATUS_SUCCESS;
  1674. goto ArbiterInitializeAllocationContextEnd;
  1675. }
  1676. FirstConfigurationListEntry =
  1677. Device->ResourceRequirements->RequirementListListHead.Next;
  1678. FirstConfiguration = LIST_VALUE(FirstConfigurationListEntry,
  1679. RESOURCE_REQUIREMENT_LIST,
  1680. ListEntry);
  1681. //
  1682. // Loop through once to find out how many requirements are in this list.
  1683. //
  1684. RequirementCount = 0;
  1685. CurrentEntry = FirstConfiguration->RequirementListHead.Next;
  1686. while (CurrentEntry != &(FirstConfiguration->RequirementListHead)) {
  1687. RequirementCount += 1;
  1688. CurrentEntry = CurrentEntry->Next;
  1689. }
  1690. if (RequirementCount == 0) {
  1691. Status = STATUS_SUCCESS;
  1692. goto ArbiterInitializeAllocationContextEnd;
  1693. }
  1694. //
  1695. // Create the arrays.
  1696. //
  1697. Status = IopArbiterResizeAllocationContext(Context, 1, RequirementCount);
  1698. if (!KSUCCESS(Status)) {
  1699. goto ArbiterInitializeAllocationContextEnd;
  1700. }
  1701. //
  1702. // Initialize the requirement list.
  1703. //
  1704. CurrentEntry = FirstConfiguration->RequirementListHead.Next;
  1705. while (CurrentEntry != &(FirstConfiguration->RequirementListHead)) {
  1706. Requirement = LIST_VALUE(CurrentEntry, RESOURCE_REQUIREMENT, ListEntry);
  1707. CurrentEntry = CurrentEntry->Next;
  1708. IopArbiterAddRequirement(Context, Requirement, Device);
  1709. }
  1710. Status = STATUS_SUCCESS;
  1711. ArbiterInitializeAllocationContextEnd:
  1712. if (!KSUCCESS(Status)) {
  1713. if (Context != NULL) {
  1714. if (Context->Device != NULL) {
  1715. MmFreePagedPool(Context->Device);
  1716. }
  1717. if (Context->Requirements != NULL) {
  1718. MmFreePagedPool(Context->Requirements);
  1719. }
  1720. MmFreePagedPool(Context);
  1721. Context = NULL;
  1722. }
  1723. }
  1724. *NewContext = Context;
  1725. return Status;
  1726. }
  1727. VOID
  1728. IopArbiterDestroyAllocationContext (
  1729. PARBITER_ALLOCATION_CONTEXT Context
  1730. )
  1731. /*++
  1732. Routine Description:
  1733. This routine destroys an arbiter allocation context.
  1734. Arguments:
  1735. Context - Supplies a pointer to the arbiter allocation context to release.
  1736. Return Value:
  1737. None.
  1738. --*/
  1739. {
  1740. if (Context->Device != NULL) {
  1741. MmFreePagedPool(Context->Device);
  1742. }
  1743. if (Context->Requirements != NULL) {
  1744. MmFreePagedPool(Context->Requirements);
  1745. }
  1746. MmFreePagedPool(Context);
  1747. return;
  1748. }
  1749. KSTATUS
  1750. IopArbiterSatisfyAllocationContext (
  1751. PARBITER_ALLOCATION_CONTEXT Context
  1752. )
  1753. /*++
  1754. Routine Description:
  1755. This routine attempts to allocate all the resource requirements currently
  1756. in the allocation context.
  1757. Arguments:
  1758. Context - Supplies a pointer to the arbiter allocation context to attempt
  1759. to satisfy.
  1760. Return Value:
  1761. STATUS_SUCCESS if all resource requirements were satisfied.
  1762. STATUS_UNSUCCESSFUL if not all resource requirements could be satisfied.
  1763. Other error codes on other failures.
  1764. --*/
  1765. {
  1766. BOOL AllocationFailed;
  1767. PRESOURCE_ARBITER Arbiter;
  1768. PARBITER_ALLOCATION_ARBITER_DATA ArbiterData;
  1769. ULONG ArbiterIndex;
  1770. PRESOURCE_REQUIREMENT CurrentAlternative;
  1771. PRESOURCE_REQUIREMENT Requirement;
  1772. PARBITER_ALLOCATION_REQUIREMENT RequirementData;
  1773. ULONG RequirementIndex;
  1774. KSTATUS Status;
  1775. AllocationFailed = FALSE;
  1776. for (ArbiterIndex = 0;
  1777. ArbiterIndex < Context->ArbiterCount;
  1778. ArbiterIndex += 1) {
  1779. Context->ArbiterData[ArbiterIndex].AmountNotAllocated = 0;
  1780. }
  1781. //
  1782. // Prioritize the requirements.
  1783. //
  1784. IopArbiterSortRequirements(Context);
  1785. //
  1786. // Loop through every requirement in the array and attempt to create an
  1787. // allocation for it.
  1788. //
  1789. for (RequirementIndex = 0;
  1790. RequirementIndex < Context->RequirementCount;
  1791. RequirementIndex += 1) {
  1792. //
  1793. // Prefer the boot allocations.
  1794. //
  1795. Status = IopArbiterTryBootAllocation(Context, RequirementIndex);
  1796. if (KSUCCESS(Status)) {
  1797. continue;
  1798. }
  1799. RequirementData = &(Context->Requirements[RequirementIndex]);
  1800. Requirement = RequirementData->Requirement;
  1801. ArbiterData = IOP_GET_ARBITER_DATA(Context, RequirementData);
  1802. Arbiter = ArbiterData->Arbiter;
  1803. ASSERT(Arbiter != NULL);
  1804. //
  1805. // Loop through every possible alternative in the list trying to make
  1806. // one stick.
  1807. //
  1808. Status = STATUS_UNSUCCESSFUL;
  1809. CurrentAlternative = Requirement;
  1810. while (CurrentAlternative != NULL) {
  1811. Status = IopArbiterAllocateSpace(Context,
  1812. RequirementIndex,
  1813. CurrentAlternative);
  1814. if (KSUCCESS(Status)) {
  1815. break;
  1816. }
  1817. CurrentAlternative = IoGetNextResourceRequirementAlternative(
  1818. Requirement,
  1819. CurrentAlternative);
  1820. }
  1821. //
  1822. // If nothing stuck, remember that something failed, and by how much.
  1823. //
  1824. if (!KSUCCESS(Status)) {
  1825. AllocationFailed = TRUE;
  1826. ArbiterData->AmountNotAllocated += Requirement->Length;
  1827. }
  1828. }
  1829. //
  1830. // If not all allocations were made, free them all.
  1831. //
  1832. if (AllocationFailed != FALSE) {
  1833. IopArbiterClearContextAllocations(Context);
  1834. Status = STATUS_UNSUCCESSFUL;
  1835. //
  1836. // If the allocations were successful, link them into the device's arbiter
  1837. // entry list. Don't worry about the order for now.
  1838. //
  1839. } else {
  1840. IopArbiterLinkContextAllocations(Context);
  1841. Status = STATUS_SUCCESS;
  1842. }
  1843. return Status;
  1844. }
  1845. VOID
  1846. IopArbiterSortRequirements (
  1847. PARBITER_ALLOCATION_CONTEXT Context
  1848. )
  1849. /*++
  1850. Routine Description:
  1851. This routine sorts all the resource requirements in an allocation context,
  1852. prioritizing them by their ratio of requirement to possible spots.
  1853. Arguments:
  1854. Context - Supplies a pointer to the arbiter allocation context to sort.
  1855. Return Value:
  1856. None.
  1857. --*/
  1858. {
  1859. ULONG FastIndex;
  1860. PARBITER_ALLOCATION_REQUIREMENT FirstRequirement;
  1861. BOOL InWrongOrder;
  1862. PARBITER_ALLOCATION_REQUIREMENT SecondRequirement;
  1863. ULONG SlowIndex;
  1864. ARBITER_ALLOCATION_REQUIREMENT Swap;
  1865. if (Context->RequirementCount == 0) {
  1866. return;
  1867. }
  1868. //
  1869. // Surely you can implement a better sort than this ridiculously lame one.
  1870. //
  1871. for (SlowIndex = 0;
  1872. SlowIndex < Context->RequirementCount - 1;
  1873. SlowIndex += 1) {
  1874. FirstRequirement = &(Context->Requirements[SlowIndex]);
  1875. for (FastIndex = SlowIndex + 1;
  1876. FastIndex < Context->RequirementCount;
  1877. FastIndex += 1) {
  1878. SecondRequirement = &(Context->Requirements[FastIndex]);
  1879. //
  1880. // The two are in the wrong order if the second requirement is
  1881. // greater than the first.
  1882. //
  1883. InWrongOrder = IopArbiterIsFirstRequirementHigherPriority(
  1884. SecondRequirement->Requirement,
  1885. FirstRequirement->Requirement);
  1886. //
  1887. // Swap the entries if they're in the wrong order.
  1888. //
  1889. if (InWrongOrder != FALSE) {
  1890. RtlCopyMemory(&Swap,
  1891. FirstRequirement,
  1892. sizeof(ARBITER_ALLOCATION_REQUIREMENT));
  1893. RtlCopyMemory(FirstRequirement,
  1894. SecondRequirement,
  1895. sizeof(ARBITER_ALLOCATION_REQUIREMENT));
  1896. RtlCopyMemory(SecondRequirement,
  1897. &Swap,
  1898. sizeof(ARBITER_ALLOCATION_REQUIREMENT));
  1899. FirstRequirement = SecondRequirement;
  1900. }
  1901. }
  1902. }
  1903. return;
  1904. }
  1905. BOOL
  1906. IopArbiterIsFirstRequirementHigherPriority (
  1907. PRESOURCE_REQUIREMENT FirstRequirement,
  1908. PRESOURCE_REQUIREMENT SecondRequirement
  1909. )
  1910. /*++
  1911. Routine Description:
  1912. This routine compares two resource requirements and determines if the first
  1913. requirement is a higher priority allocation to satisfy than the second.
  1914. Arguments:
  1915. FirstRequirement - Supplies a pointer to the requirement to be compared.
  1916. SecondRequirement - Supplies a pointer to the requirement to compare with.
  1917. Return Value:
  1918. TRUE if the first requirement is of higher priority than the second.
  1919. FALSE if the first requirement is of equal or lesser priority than the
  1920. second.
  1921. --*/
  1922. {
  1923. ULONGLONG Alignment;
  1924. ULONGLONG FirstRequirementPossibilities;
  1925. ULONGLONG SecondRequirementPossibilities;
  1926. //
  1927. // Sort first by requirement type. The lower the type value the higher the
  1928. // priority.
  1929. //
  1930. if (FirstRequirement->Type != SecondRequirement->Type) {
  1931. if (FirstRequirement->Type < SecondRequirement->Type) {
  1932. return TRUE;
  1933. }
  1934. return FALSE;
  1935. }
  1936. //
  1937. // Get each requirement's priority. The priority is based on the number of
  1938. // different positions this requirement could take in it's range of
  1939. // possibilities.
  1940. // TODO: Add alternatives into the mix here.
  1941. //
  1942. Alignment = FirstRequirement->Alignment;
  1943. if (Alignment == 0) {
  1944. Alignment = 1;
  1945. }
  1946. FirstRequirementPossibilities =
  1947. (FirstRequirement->Maximum - FirstRequirement->Minimum -
  1948. FirstRequirement->Length) / Alignment;
  1949. Alignment = SecondRequirement->Alignment;
  1950. if (Alignment == 0) {
  1951. Alignment = 1;
  1952. }
  1953. SecondRequirementPossibilities =
  1954. (SecondRequirement->Maximum - SecondRequirement->Minimum -
  1955. SecondRequirement->Length) / Alignment;
  1956. if (FirstRequirementPossibilities < SecondRequirementPossibilities) {
  1957. return TRUE;
  1958. }
  1959. return FALSE;
  1960. }
  1961. KSTATUS
  1962. IopArbiterRipUpReservedAllocations (
  1963. PARBITER_ALLOCATION_CONTEXT Context
  1964. )
  1965. /*++
  1966. Routine Description:
  1967. This routine surveys all the arbiters in the given context that have failed.
  1968. It rips up all reserved allocations in those arbiters (removing them from
  1969. the device's arbiter entry list), and adds the corresponding resource
  1970. requirements to the context. The hope is that by completely rearranging
  1971. all the furniture in the room there will be space for that one more chair.
  1972. Arguments:
  1973. Context - Supplies a pointer to the arbiter allocation context to attempt
  1974. to satisfy.
  1975. Return Value:
  1976. Status code.
  1977. --*/
  1978. {
  1979. PRESOURCE_ARBITER Arbiter;
  1980. ULONG ArbiterIndex;
  1981. PLIST_ENTRY CurrentEntry;
  1982. ULONG DeviceCount;
  1983. PARBITER_ENTRY Entry;
  1984. ULONG RequirementCount;
  1985. KSTATUS Status;
  1986. //
  1987. // Loop through all arbiters once to figure out the new total number of
  1988. // requirements and devices involved. One might think that a nice
  1989. // optimization might be to avoid ripping up arbiters that aren't failing.
  1990. // Unfortunately this is not possible, since if a previously uninvolved
  1991. // device's allocations get ripped up, ALL of its allocations need to be
  1992. // ripped up (since it might get adjusted down a configuration).
  1993. //
  1994. RequirementCount = Context->RequirementCount;
  1995. DeviceCount = Context->DeviceCount;
  1996. for (ArbiterIndex = 0;
  1997. ArbiterIndex < Context->ArbiterCount;
  1998. ArbiterIndex += 1) {
  1999. Arbiter = Context->ArbiterData[ArbiterIndex].Arbiter;
  2000. if (Arbiter == NULL) {
  2001. continue;
  2002. }
  2003. //
  2004. // Loop through every entry in the arbiter.
  2005. //
  2006. CurrentEntry = Arbiter->EntryListHead.Next;
  2007. while (CurrentEntry != &(Arbiter->EntryListHead)) {
  2008. Entry = LIST_VALUE(CurrentEntry, ARBITER_ENTRY, ListEntry);
  2009. CurrentEntry = CurrentEntry->Next;
  2010. if (Entry->Type != ArbiterSpaceReserved) {
  2011. continue;
  2012. }
  2013. RequirementCount += 1;
  2014. //
  2015. // Assume that every new requirement belongs to a unique device.
  2016. // This is almost certainly too much, but will simply result in an
  2017. // array that is allocated to be a bit too big.
  2018. //
  2019. DeviceCount += 1;
  2020. }
  2021. }
  2022. //
  2023. // Resize the arrays to fit the new stuff.
  2024. //
  2025. Status = IopArbiterResizeAllocationContext(Context,
  2026. DeviceCount,
  2027. RequirementCount);
  2028. if (!KSUCCESS(Status)) {
  2029. goto ArbiterRipUpReservedAllocationsEnd;
  2030. }
  2031. //
  2032. // Loop through the arbiters again now that everything is prepared for the
  2033. // new allocations. Release anything in the arbiters that hasn't yet been
  2034. // given to a device driver.
  2035. //
  2036. for (ArbiterIndex = 0;
  2037. ArbiterIndex < Context->ArbiterCount;
  2038. ArbiterIndex += 1) {
  2039. Arbiter = Context->ArbiterData[ArbiterIndex].Arbiter;
  2040. if (Arbiter == NULL) {
  2041. continue;
  2042. }
  2043. //
  2044. // Loop through every entry in the arbiter.
  2045. //
  2046. CurrentEntry = Arbiter->EntryListHead.Next;
  2047. while (CurrentEntry != &(Arbiter->EntryListHead)) {
  2048. Entry = LIST_VALUE(CurrentEntry, ARBITER_ENTRY, ListEntry);
  2049. CurrentEntry = CurrentEntry->Next;
  2050. if (Entry->Type != ArbiterSpaceReserved) {
  2051. continue;
  2052. }
  2053. IopArbiterAddRequirement(Context,
  2054. Entry->CorrespondingRequirement,
  2055. Entry->Device);
  2056. //
  2057. // Remove the entry.
  2058. //
  2059. LIST_REMOVE(&(Entry->ConfigurationListEntry));
  2060. IopArbiterFreeEntry(Arbiter, Entry);
  2061. }
  2062. }
  2063. Status = STATUS_SUCCESS;
  2064. ArbiterRipUpReservedAllocationsEnd:
  2065. return Status;
  2066. }
  2067. KSTATUS
  2068. IopArbiterExpandFailingArbiters (
  2069. PARBITER_ALLOCATION_CONTEXT Context
  2070. )
  2071. /*++
  2072. Routine Description:
  2073. This routine attempts to create more space in every arbiter that does not
  2074. have enough space.
  2075. Arguments:
  2076. Context - Supplies a pointer to the allocation context to work with.
  2077. Return Value:
  2078. Status code.
  2079. --*/
  2080. {
  2081. ULONGLONG AmountNeeded;
  2082. PRESOURCE_ARBITER Arbiter;
  2083. PARBITER_ALLOCATION_ARBITER_DATA ArbiterData;
  2084. ULONG ArbiterIndex;
  2085. ULONGLONG ArbiterSize;
  2086. PLIST_ENTRY CurrentEntry;
  2087. PARBITER_ENTRY Entry;
  2088. for (ArbiterIndex = 0;
  2089. ArbiterIndex < Context->ArbiterCount;
  2090. ArbiterIndex += 1) {
  2091. ArbiterData = &(Context->ArbiterData[ArbiterIndex]);
  2092. //
  2093. // If the arbiter doesn't have a problem, don't touch it.
  2094. //
  2095. if (ArbiterData->AmountNotAllocated == 0) {
  2096. continue;
  2097. }
  2098. Arbiter = ArbiterData->Arbiter;
  2099. ASSERT(Arbiter != NULL);
  2100. //
  2101. // Loop through every entry in the arbiter.
  2102. //
  2103. ArbiterSize = 0;
  2104. CurrentEntry = Arbiter->EntryListHead.Next;
  2105. while (CurrentEntry != &(Arbiter->EntryListHead)) {
  2106. Entry = LIST_VALUE(CurrentEntry, ARBITER_ENTRY, ListEntry);
  2107. CurrentEntry = CurrentEntry->Next;
  2108. if (Entry->Type == ArbiterSpaceFree) {
  2109. ArbiterSize += Entry->Length;
  2110. continue;
  2111. }
  2112. break;
  2113. }
  2114. //
  2115. // If there were allocations in the arbiter, then it cannot be
  2116. // resized.
  2117. //
  2118. if (CurrentEntry != &(Arbiter->EntryListHead)) {
  2119. continue;
  2120. }
  2121. //
  2122. // Ask for more space, the old size plus double the amount not
  2123. // allocated.
  2124. //
  2125. AmountNeeded = ArbiterSize + (ArbiterData->AmountNotAllocated * 2);
  2126. IopArbiterExpandSpace(Arbiter, AmountNeeded);
  2127. }
  2128. return STATUS_SUCCESS;
  2129. }
  2130. KSTATUS
  2131. IopArbiterExpandSpace (
  2132. PRESOURCE_ARBITER Arbiter,
  2133. ULONGLONG AmountNeeded
  2134. )
  2135. /*++
  2136. Routine Description:
  2137. This routine asks the arbiter's device for more space to put into the
  2138. arbiter. On success, the arbiter will have more free space.
  2139. Arguments:
  2140. Arbiter - Supplies a pointer to the arbiter in need.
  2141. AmountNeeded - Supplies the amount of additional space needed.
  2142. Return Value:
  2143. Status code.
  2144. --*/
  2145. {
  2146. return STATUS_NOT_IMPLEMENTED;
  2147. }
  2148. KSTATUS
  2149. IopArbiterLimitResourceHog (
  2150. PARBITER_ALLOCATION_CONTEXT Context
  2151. )
  2152. /*++
  2153. Routine Description:
  2154. This routine starts making compromises for the sake of device resource
  2155. allocation. It finds the most congested resource, looks for the biggest
  2156. potential consumer of that resource, and knocks that device down a
  2157. configuration.
  2158. Arguments:
  2159. Context - Supplies a pointer to the context causing the resource squeeze.
  2160. Return Value:
  2161. Status code.
  2162. --*/
  2163. {
  2164. PRESOURCE_ARBITER Arbiter;
  2165. PARBITER_ALLOCATION_ARBITER_DATA ArbiterData;
  2166. ULONG ArbiterIndex;
  2167. ULONGLONG BiggestRequirementAmount;
  2168. ULONG BiggestRequirementIndex;
  2169. PRESOURCE_REQUIREMENT_LIST Configuration;
  2170. PLIST_ENTRY CurrentEntry;
  2171. PDEVICE Device;
  2172. ULONG DeviceIndex;
  2173. ULONG EndRequirementIndex;
  2174. PLIST_ENTRY NextConfigurationListEntry;
  2175. BOOL RemoveDevice;
  2176. PRESOURCE_REQUIREMENT Requirement;
  2177. ULONG RequirementCount;
  2178. PARBITER_ALLOCATION_REQUIREMENT RequirementData;
  2179. ULONG RequirementIndex;
  2180. KSTATUS Status;
  2181. PRESOURCE_ARBITER TightestArbiter;
  2182. ULONGLONG TightestArbiterAmount;
  2183. //
  2184. // Find the tightest arbiter.
  2185. //
  2186. TightestArbiter = NULL;
  2187. TightestArbiterAmount = 0;
  2188. for (ArbiterIndex = 0;
  2189. ArbiterIndex < Context->ArbiterCount;
  2190. ArbiterIndex += 1) {
  2191. ArbiterData = &(Context->ArbiterData[ArbiterIndex]);
  2192. Arbiter = ArbiterData->Arbiter;
  2193. if (ArbiterData->AmountNotAllocated > TightestArbiterAmount) {
  2194. TightestArbiterAmount = ArbiterData->AmountNotAllocated;
  2195. TightestArbiter = Arbiter;
  2196. ASSERT(Arbiter != NULL);
  2197. }
  2198. }
  2199. ASSERT(TightestArbiter != NULL);
  2200. //
  2201. // Find the biggest requirement for that arbiter that's not already in the
  2202. // last configuration.
  2203. //
  2204. RemoveDevice = FALSE;
  2205. BiggestRequirementAmount = 0;
  2206. BiggestRequirementIndex = -1;
  2207. for (RequirementIndex = 0;
  2208. RequirementIndex < Context->RequirementCount;
  2209. RequirementIndex += 1) {
  2210. RequirementData = &(Context->Requirements[RequirementIndex]);
  2211. Device = IOP_ARBITER_GET_DEVICE(Context, RequirementData);
  2212. Requirement = RequirementData->Requirement;
  2213. DeviceIndex = RequirementData->DeviceIndex;
  2214. ASSERT(DeviceIndex < Context->DeviceCount);
  2215. //
  2216. // Skip if it's the last configuration.
  2217. //
  2218. if (Context->CurrentDeviceConfiguration[DeviceIndex]->ListEntry.Next ==
  2219. &(Device->ResourceRequirements->RequirementListListHead)) {
  2220. continue;
  2221. }
  2222. //
  2223. // Remember if it's the new big guy.
  2224. //
  2225. if (Requirement->Length > BiggestRequirementAmount) {
  2226. BiggestRequirementAmount = Requirement->Length;
  2227. BiggestRequirementIndex = RequirementIndex;
  2228. }
  2229. }
  2230. //
  2231. // If there is no big guy, then everyone is at their worst configuration.
  2232. // Find a device to knock out of the race.
  2233. //
  2234. if (BiggestRequirementIndex == -1) {
  2235. RemoveDevice = TRUE;
  2236. BiggestRequirementAmount = 0;
  2237. BiggestRequirementIndex = -1;
  2238. for (RequirementIndex = 0;
  2239. RequirementIndex < Context->RequirementCount;
  2240. RequirementIndex += 1) {
  2241. RequirementData = &(Context->Requirements[RequirementIndex]);
  2242. Device = IOP_ARBITER_GET_DEVICE(Context, RequirementData);
  2243. Requirement = RequirementData->Requirement;
  2244. DeviceIndex = RequirementData->DeviceIndex;
  2245. ASSERT(DeviceIndex < Context->DeviceCount);
  2246. //
  2247. // Remember if it's the new big guy.
  2248. //
  2249. if (Requirement->Length > BiggestRequirementAmount) {
  2250. BiggestRequirementAmount = Requirement->Length;
  2251. BiggestRequirementIndex = RequirementIndex;
  2252. }
  2253. }
  2254. }
  2255. ASSERT(BiggestRequirementIndex != -1);
  2256. //
  2257. // Remove all requirements associated with the device at its old
  2258. // configuration.
  2259. //
  2260. RequirementData = &(Context->Requirements[BiggestRequirementIndex]);
  2261. Device = IOP_ARBITER_GET_DEVICE(Context, RequirementData);
  2262. DeviceIndex = RequirementData->DeviceIndex;
  2263. for (RequirementIndex = 0;
  2264. RequirementIndex < Context->RequirementCount;
  2265. NOTHING) {
  2266. //
  2267. // If this is the magic device's requirement, move the requirement from
  2268. // the end of the array on top of this one.
  2269. //
  2270. RequirementData = &(Context->Requirements[RequirementIndex]);
  2271. if (IOP_ARBITER_GET_DEVICE(Context, RequirementData) == Device) {
  2272. ASSERT(RequirementData->Allocation == NULL);
  2273. EndRequirementIndex = Context->RequirementCount - 1;
  2274. if (EndRequirementIndex != RequirementIndex) {
  2275. RtlCopyMemory(RequirementData,
  2276. &(Context->Requirements[EndRequirementIndex]),
  2277. sizeof(ARBITER_ALLOCATION_REQUIREMENT));
  2278. }
  2279. Context->RequirementCount -= 1;
  2280. //
  2281. // Only advance to the next index if that requirement wasn't just
  2282. // replaced.
  2283. //
  2284. } else {
  2285. RequirementIndex += 1;
  2286. }
  2287. }
  2288. ASSERT(DeviceIndex < Context->DeviceCount);
  2289. //
  2290. // If it's getting desperate, remove the device itself.
  2291. //
  2292. if (RemoveDevice != FALSE) {
  2293. Context->Device[DeviceIndex] = NULL;
  2294. Context->CurrentDeviceConfiguration[DeviceIndex] = NULL;
  2295. //
  2296. // Notch the configuration down a tick, and add all those requirements.
  2297. //
  2298. } else {
  2299. Configuration = Context->CurrentDeviceConfiguration[DeviceIndex];
  2300. NextConfigurationListEntry = Configuration->ListEntry.Next;
  2301. ASSERT(NextConfigurationListEntry !=
  2302. &(Device->ResourceRequirements->RequirementListListHead));
  2303. Configuration = LIST_VALUE(NextConfigurationListEntry,
  2304. RESOURCE_REQUIREMENT_LIST,
  2305. ListEntry);
  2306. Context->CurrentDeviceConfiguration[DeviceIndex] = Configuration;
  2307. //
  2308. // Loop through the configuration once to determine how many
  2309. // requirements there are.
  2310. //
  2311. RequirementCount = 0;
  2312. CurrentEntry = Configuration->RequirementListHead.Next;
  2313. while (CurrentEntry != &(Configuration->RequirementListHead)) {
  2314. RequirementCount += 1;
  2315. CurrentEntry = CurrentEntry->Next;
  2316. }
  2317. //
  2318. // Resize the arrays.
  2319. //
  2320. Status = IopArbiterResizeAllocationContext(
  2321. Context,
  2322. Context->DeviceCount,
  2323. Context->RequirementCount + RequirementCount);
  2324. if (!KSUCCESS(Status)) {
  2325. goto ArbiterLimitResourceHogEnd;
  2326. }
  2327. //
  2328. // Loop through again and add the resource requirements.
  2329. //
  2330. CurrentEntry = Configuration->RequirementListHead.Next;
  2331. while (CurrentEntry != &(Configuration->RequirementListHead)) {
  2332. Requirement = LIST_VALUE(CurrentEntry,
  2333. RESOURCE_REQUIREMENT,
  2334. ListEntry);
  2335. CurrentEntry = CurrentEntry->Next;
  2336. IopArbiterAddRequirement(Context, Requirement, Device);
  2337. }
  2338. }
  2339. Status = STATUS_SUCCESS;
  2340. ArbiterLimitResourceHogEnd:
  2341. return Status;
  2342. }
  2343. KSTATUS
  2344. IopArbiterResizeAllocationContext (
  2345. PARBITER_ALLOCATION_CONTEXT Context,
  2346. ULONG NewDeviceCount,
  2347. ULONG NewRequirementCount
  2348. )
  2349. /*++
  2350. Routine Description:
  2351. This routine resizes the appropriate arrays in the given arbiter allocation
  2352. context. This routine allocates new arrays of the given size, copies the
  2353. old contents over, and frees the old arrays. It does not modify the
  2354. device or requirement count variables.
  2355. Arguments:
  2356. Context - Supplies a pointer to the context to adjust.
  2357. NewDeviceCount - Supplies the new device count.
  2358. NewRequirementCount - Supplies the new resource requirement count.
  2359. Return Value:
  2360. Status code.
  2361. --*/
  2362. {
  2363. ULONG AllocationSize;
  2364. UINTN CopySize;
  2365. PARBITER_ALLOCATION_ARBITER_DATA NewArbiterDataArray;
  2366. PRESOURCE_REQUIREMENT_LIST *NewCurrentDeviceConfigurationArray;
  2367. PDEVICE *NewDeviceArray;
  2368. PARBITER_ALLOCATION_REQUIREMENT NewRequirementArray;
  2369. ULONG OldRequirementCount;
  2370. KSTATUS Status;
  2371. NewDeviceArray = NULL;
  2372. NewRequirementArray = NULL;
  2373. //
  2374. // Allocate the new arrays in the context.
  2375. //
  2376. AllocationSize = (sizeof(PDEVICE) * NewDeviceCount) +
  2377. (sizeof(PRESOURCE_REQUIREMENT_LIST) * NewDeviceCount);
  2378. NewDeviceArray = MmAllocatePagedPool(AllocationSize,
  2379. ARBITER_ALLOCATION_TAG);
  2380. if (NewDeviceArray == NULL) {
  2381. Status = STATUS_INSUFFICIENT_RESOURCES;
  2382. goto ArbiterResizeAllocationContextEnd;
  2383. }
  2384. RtlZeroMemory(NewDeviceArray, AllocationSize);
  2385. NewCurrentDeviceConfigurationArray =
  2386. (PRESOURCE_REQUIREMENT_LIST *)(NewDeviceArray + NewDeviceCount);
  2387. AllocationSize = (sizeof(ARBITER_ALLOCATION_REQUIREMENT) *
  2388. NewRequirementCount) +
  2389. (sizeof(ARBITER_ALLOCATION_ARBITER_DATA) *
  2390. NewRequirementCount);
  2391. NewRequirementArray = MmAllocatePagedPool(AllocationSize,
  2392. ARBITER_ALLOCATION_TAG);
  2393. if (NewRequirementArray == NULL) {
  2394. Status = STATUS_INSUFFICIENT_RESOURCES;
  2395. goto ArbiterResizeAllocationContextEnd;
  2396. }
  2397. RtlZeroMemory(NewRequirementArray, AllocationSize);
  2398. NewArbiterDataArray =
  2399. (PARBITER_ALLOCATION_ARBITER_DATA)(NewRequirementArray +
  2400. NewRequirementCount);
  2401. //
  2402. // Copy the old arrays into the new arrays. The allocations are not
  2403. // copied because they're all NULL at this point.
  2404. //
  2405. if (Context->Device != NULL) {
  2406. RtlCopyMemory(NewDeviceArray,
  2407. Context->Device,
  2408. Context->DeviceCount * sizeof(PDEVICE));
  2409. RtlCopyMemory(
  2410. NewCurrentDeviceConfigurationArray,
  2411. Context->CurrentDeviceConfiguration,
  2412. Context->DeviceCount * sizeof(PRESOURCE_REQUIREMENT_LIST));
  2413. MmFreePagedPool(Context->Device);
  2414. }
  2415. if (Context->Requirements != NULL) {
  2416. OldRequirementCount = Context->RequirementCount;
  2417. CopySize = OldRequirementCount * sizeof(ARBITER_ALLOCATION_REQUIREMENT);
  2418. RtlCopyMemory(NewRequirementArray, Context->Requirements, CopySize);
  2419. CopySize = Context->ArbiterCount *
  2420. sizeof(ARBITER_ALLOCATION_ARBITER_DATA);
  2421. RtlCopyMemory(NewArbiterDataArray, Context->ArbiterData, CopySize);
  2422. MmFreePagedPool(Context->Requirements);
  2423. }
  2424. //
  2425. // Replace the old arrays with the newly improved bigger arrays. Leave
  2426. // the sizes alone as they will be expanded as they go.
  2427. //
  2428. Context->Device = NewDeviceArray;
  2429. Context->CurrentDeviceConfiguration = NewCurrentDeviceConfigurationArray;
  2430. Context->Requirements = NewRequirementArray;
  2431. Context->ArbiterData = NewArbiterDataArray;
  2432. Status = STATUS_SUCCESS;
  2433. ArbiterResizeAllocationContextEnd:
  2434. if (!KSUCCESS(Status)) {
  2435. if (NewDeviceArray != NULL) {
  2436. MmFreePagedPool(NewDeviceArray);
  2437. }
  2438. if (NewRequirementArray != NULL) {
  2439. MmFreePagedPool(NewRequirementArray);
  2440. }
  2441. }
  2442. return Status;
  2443. }
  2444. VOID
  2445. IopArbiterMarkSelectedConfigurations (
  2446. PARBITER_ALLOCATION_CONTEXT Context
  2447. )
  2448. /*++
  2449. Routine Description:
  2450. This routine marks which resource configuration was chosen in each device
  2451. involved.
  2452. Note: By adjusting resource configurations of devices that had gotten ripped
  2453. up, there is an assumption that a device and all of its siblings
  2454. share the same set of arbiters. If this is not true, then the arbiters
  2455. will return invalid configurations. For example, a first device is
  2456. reserved resources from its first configuration, then a second device
  2457. with a different set of arbiters comes in, the first device's
  2458. allocations are ripped up (but only those in the same set of
  2459. arbiters that the second device is working with), and then the
  2460. resource configuration of the first device is adjusted down. This
  2461. would result in the first device being given some resources from its
  2462. first configuration (from the arbiters that didn't overlap with the
  2463. second device) and other resource from a lower configuration.
  2464. Arguments:
  2465. Context - Supplies a pointer to the allocation context that was just
  2466. satisfied.
  2467. Return Value:
  2468. None.
  2469. --*/
  2470. {
  2471. PDEVICE Device;
  2472. ULONG DeviceIndex;
  2473. for (DeviceIndex = 0;
  2474. DeviceIndex < Context->DeviceCount;
  2475. DeviceIndex += 1) {
  2476. Device = Context->Device[DeviceIndex];
  2477. if (Device == NULL) {
  2478. continue;
  2479. }
  2480. Device->SelectedConfiguration =
  2481. Context->CurrentDeviceConfiguration[DeviceIndex];
  2482. }
  2483. return;
  2484. }
  2485. VOID
  2486. IopArbiterMatchAllocationsToRequirements (
  2487. PDEVICE Device,
  2488. PULONG RequirementCount
  2489. )
  2490. /*++
  2491. Routine Description:
  2492. This routine rearranges the list of the device's arbiter entries so that
  2493. they are in the same order as the device's resource requirement list.
  2494. It can also optionally return the number of resource requirements the
  2495. device has.
  2496. Arguments:
  2497. Device - Supplies a pointer to the device.
  2498. RequirementCount - Supplies a pointer where the number of requirements
  2499. will be returned.
  2500. Return Value:
  2501. Status code.
  2502. --*/
  2503. {
  2504. PARBITER_ENTRY CurrentAllocation;
  2505. PLIST_ENTRY CurrentAllocationEntry;
  2506. PRESOURCE_REQUIREMENT CurrentRequirement;
  2507. PLIST_ENTRY CurrentRequirementEntry;
  2508. ULONG NumberOfRequirements;
  2509. PLIST_ENTRY PreviousAllocationEntry;
  2510. PRESOURCE_REQUIREMENT_LIST RequirementList;
  2511. RequirementList = Device->SelectedConfiguration;
  2512. NumberOfRequirements = 0;
  2513. //
  2514. // Loop through every requirement in the requirement list.
  2515. //
  2516. PreviousAllocationEntry = &(Device->ArbiterAllocationListHead);
  2517. CurrentRequirementEntry = RequirementList->RequirementListHead.Next;
  2518. while (CurrentRequirementEntry != &(RequirementList->RequirementListHead)) {
  2519. CurrentRequirement = LIST_VALUE(CurrentRequirementEntry,
  2520. RESOURCE_REQUIREMENT,
  2521. ListEntry);
  2522. CurrentRequirementEntry = CurrentRequirementEntry->Next;
  2523. NumberOfRequirements += 1;
  2524. //
  2525. // Loop through the remaining arbiter allocations to find the one that
  2526. // corresponds to this requirement.
  2527. //
  2528. CurrentAllocationEntry = PreviousAllocationEntry->Next;
  2529. while (CurrentAllocationEntry != &(Device->ArbiterAllocationListHead)) {
  2530. CurrentAllocation = LIST_VALUE(CurrentAllocationEntry,
  2531. ARBITER_ENTRY,
  2532. ConfigurationListEntry);
  2533. if (CurrentAllocation->CorrespondingRequirement ==
  2534. CurrentRequirement) {
  2535. LIST_REMOVE(CurrentAllocationEntry);
  2536. INSERT_AFTER(CurrentAllocationEntry, PreviousAllocationEntry);
  2537. break;
  2538. }
  2539. CurrentAllocationEntry = CurrentAllocationEntry->Next;
  2540. }
  2541. ASSERT(CurrentAllocationEntry != &(Device->ArbiterAllocationListHead));
  2542. PreviousAllocationEntry = PreviousAllocationEntry->Next;
  2543. }
  2544. if (RequirementCount != NULL) {
  2545. *RequirementCount = NumberOfRequirements;
  2546. }
  2547. return;
  2548. }
  2549. VOID
  2550. IopArbiterInitializeResourceAllocation (
  2551. PARBITER_ENTRY ArbiterEntry,
  2552. PRESOURCE_ALLOCATION ResourceAllocation
  2553. )
  2554. /*++
  2555. Routine Description:
  2556. This routine initializes a resource allocation based on an arbiter entry.
  2557. Arguments:
  2558. ResourceType - Supplies the resource type of the allocation to initialize.
  2559. ArbiterEntry - Supplies a pointer to the arbiter entry to use as a template
  2560. for the resource allocation.
  2561. ResourceAllocation - Supplies a pointer where the resource allocation
  2562. corresponding to the given arbiter entry will be returned.
  2563. Return Value:
  2564. None.
  2565. --*/
  2566. {
  2567. PRESOURCE_REQUIREMENT Requirement;
  2568. Requirement = ArbiterEntry->CorrespondingRequirement;
  2569. ResourceAllocation->Type = Requirement->Type;
  2570. ResourceAllocation->Allocation = ArbiterEntry->Allocation;
  2571. ResourceAllocation->Length = ArbiterEntry->Length;
  2572. ResourceAllocation->Characteristics = ArbiterEntry->Characteristics;
  2573. ResourceAllocation->Flags = Requirement->Flags;
  2574. ResourceAllocation->Data = Requirement->Data;
  2575. ResourceAllocation->DataSize = Requirement->DataSize;
  2576. ResourceAllocation->Provider = Requirement->Provider;
  2577. return;
  2578. }
  2579. KSTATUS
  2580. IopArbiterCopyAndTranslateResources (
  2581. PRESOURCE_ALLOCATION_LIST BusLocalResources,
  2582. PRESOURCE_ALLOCATION_LIST *ProcessorLocalResources
  2583. )
  2584. /*++
  2585. Routine Description:
  2586. This routine translates a set of resources from bus local resources to
  2587. processor local resources.
  2588. Arguments:
  2589. BusLocalResources - Supplies a pointer to the bus local resources to
  2590. translate from.
  2591. ProcessorLocalResources - Supplies a pointer where a newly allocated list
  2592. of processor local resources will be returned. The caller is
  2593. responsible for destroying this resource list once it is returned.
  2594. Return Value:
  2595. Status code.
  2596. --*/
  2597. {
  2598. PRESOURCE_ALLOCATION Allocation;
  2599. KSTATUS Status;
  2600. RESOURCE_ALLOCATION TranslatedResource;
  2601. PRESOURCE_ALLOCATION_LIST TranslatedResources;
  2602. TranslatedResources = NULL;
  2603. if (BusLocalResources == NULL) {
  2604. Status = STATUS_SUCCESS;
  2605. goto ArbiterCopyAndTranslateResourcesEnd;
  2606. }
  2607. //
  2608. // Create a new resource allocation list.
  2609. //
  2610. TranslatedResources = IoCreateResourceAllocationList();
  2611. if (TranslatedResources == NULL) {
  2612. Status = STATUS_INSUFFICIENT_RESOURCES;
  2613. goto ArbiterCopyAndTranslateResourcesEnd;
  2614. }
  2615. Allocation = IoGetNextResourceAllocation(BusLocalResources, NULL);
  2616. while (Allocation != NULL) {
  2617. //
  2618. // Create a local copy of the resource and translate it.
  2619. //
  2620. RtlCopyMemory(&TranslatedResource,
  2621. Allocation,
  2622. sizeof(RESOURCE_ALLOCATION));
  2623. //
  2624. // TODO: Find the arbiter entry associated with this resource and
  2625. // apply the translation.
  2626. //
  2627. //
  2628. // Create a copy of the resource.
  2629. //
  2630. Status = IoCreateAndAddResourceAllocation(&TranslatedResource,
  2631. TranslatedResources);
  2632. if (!KSUCCESS(Status)) {
  2633. goto ArbiterCopyAndTranslateResourcesEnd;
  2634. }
  2635. //
  2636. // Get the next allocation.
  2637. //
  2638. Allocation = IoGetNextResourceAllocation(BusLocalResources, Allocation);
  2639. }
  2640. Status = STATUS_SUCCESS;
  2641. ArbiterCopyAndTranslateResourcesEnd:
  2642. if (!KSUCCESS(Status)) {
  2643. if (TranslatedResources != NULL) {
  2644. IoDestroyResourceAllocationList(TranslatedResources);
  2645. TranslatedResources = NULL;
  2646. }
  2647. }
  2648. *ProcessorLocalResources = TranslatedResources;
  2649. return Status;
  2650. }
  2651. KSTATUS
  2652. IopArbiterTryBootAllocations (
  2653. PARBITER_ALLOCATION_CONTEXT Context
  2654. )
  2655. /*++
  2656. Routine Description:
  2657. This routine attempts to use the boot allocations for a device.
  2658. Arguments:
  2659. Context - Supplies a pointer to the arbiter allocation context.
  2660. Return Value:
  2661. STATUS_SUCCESS if all the boot allocations were successfully reserved in
  2662. the arbiters.
  2663. Other errors on failure.
  2664. --*/
  2665. {
  2666. ULONG RequirementIndex;
  2667. KSTATUS Status;
  2668. //
  2669. // Loop through all the requirements.
  2670. //
  2671. for (RequirementIndex = 0;
  2672. RequirementIndex < Context->RequirementCount;
  2673. RequirementIndex += 1) {
  2674. Status = IopArbiterTryBootAllocation(Context, RequirementIndex);
  2675. if (!KSUCCESS(Status)) {
  2676. goto ArbiterTryBootAllocationsEnd;
  2677. }
  2678. }
  2679. //
  2680. // Everything worked, link the context allocations to their requirement's
  2681. // devices.
  2682. //
  2683. IopArbiterLinkContextAllocations(Context);
  2684. Status = STATUS_SUCCESS;
  2685. ArbiterTryBootAllocationsEnd:
  2686. if (!KSUCCESS(Status)) {
  2687. IopArbiterClearContextAllocations(Context);
  2688. }
  2689. return Status;
  2690. }
  2691. KSTATUS
  2692. IopArbiterTryBootAllocation (
  2693. PARBITER_ALLOCATION_CONTEXT Context,
  2694. UINTN RequirementIndex
  2695. )
  2696. /*++
  2697. Routine Description:
  2698. This routine attempts to use the boot allocation for a particular
  2699. requirement.
  2700. Arguments:
  2701. Context - Supplies a pointer to the arbiter allocation context.
  2702. RequirementIndex - Supplies the index of the requirement to try and
  2703. satisfy with a boot allocation.
  2704. Return Value:
  2705. STATUS_SUCCESS if all the boot allocations were successfully reserved in
  2706. the arbiters.
  2707. Other errors on failure.
  2708. --*/
  2709. {
  2710. PRESOURCE_ARBITER Arbiter;
  2711. PARBITER_ENTRY ArbiterEntry;
  2712. PRESOURCE_ALLOCATION BootAllocation;
  2713. BOOL Conflict;
  2714. PDEVICE Device;
  2715. PARBITER_ENTRY NewEntry;
  2716. PRESOURCE_REQUIREMENT Requirement;
  2717. PARBITER_ALLOCATION_REQUIREMENT RequirementData;
  2718. KSTATUS Status;
  2719. RequirementData = &(Context->Requirements[RequirementIndex]);
  2720. Requirement = RequirementData->Requirement;
  2721. Device = IOP_ARBITER_GET_DEVICE(Context, RequirementData);
  2722. Arbiter = IOP_ARBITER_GET_ARBITER(Context, RequirementData);
  2723. ASSERT(Arbiter != NULL);
  2724. BootAllocation = IopArbiterFindBootAllocationForRequirement(Device,
  2725. Requirement);
  2726. //
  2727. // If there's no boot allocation for this requirement or the boot
  2728. // allocation doesn't satisfy the requirement, attempt to satisfy it
  2729. // with something else.
  2730. //
  2731. if ((BootAllocation == NULL) ||
  2732. (BootAllocation->Length < Requirement->Length)) {
  2733. Status = IopArbiterAllocateSpace(Context, RequirementIndex, NULL);
  2734. goto ArbiterTryBootAllocationEnd;
  2735. }
  2736. //
  2737. // Requirements satisfied by boot allocations should not have related
  2738. // requirements.
  2739. //
  2740. ASSERT(Requirement->OwningRequirement == NULL);
  2741. //
  2742. // Find out what's in the arbiter at this location.
  2743. //
  2744. ArbiterEntry = NULL;
  2745. if (BootAllocation->Length != 0) {
  2746. ArbiterEntry = IopArbiterFindEntry(Arbiter,
  2747. BootAllocation->Allocation,
  2748. TRUE);
  2749. }
  2750. //
  2751. // If there's something there, make sure it agrees.
  2752. //
  2753. if (ArbiterEntry != NULL) {
  2754. //
  2755. // If the entry isn't free, then it had better exactly work with the
  2756. // entry there, and be shareable.
  2757. //
  2758. Conflict = FALSE;
  2759. if (ArbiterEntry->Type != ArbiterSpaceFree) {
  2760. if ((ArbiterEntry->Characteristics !=
  2761. Requirement->Characteristics) ||
  2762. ((Requirement->Flags &
  2763. RESOURCE_FLAG_NOT_SHAREABLE) != 0) ||
  2764. ((ArbiterEntry->Flags &
  2765. RESOURCE_FLAG_NOT_SHAREABLE) != 0) ||
  2766. (Requirement->Length != ArbiterEntry->Length)) {
  2767. Conflict = TRUE;
  2768. }
  2769. if ((ArbiterEntry->Allocation & (Requirement->Alignment - 1)) !=
  2770. 0) {
  2771. Conflict = TRUE;
  2772. }
  2773. //
  2774. // If different boot resources of the same device conflict with
  2775. // each other, then assume the BIOS knows what it's doing there
  2776. // and allow it.
  2777. //
  2778. if ((Conflict != FALSE) && (ArbiterEntry->Device == Device) &&
  2779. ((ArbiterEntry->Flags & RESOURCE_FLAG_BOOT) != 0)) {
  2780. Conflict = FALSE;
  2781. }
  2782. if (Conflict != FALSE) {
  2783. Status = STATUS_RANGE_CONFLICT;
  2784. goto ArbiterTryBootAllocationEnd;
  2785. }
  2786. }
  2787. //
  2788. // There is no entry, so add some free space and then allocate it. This
  2789. // gives the BIOS the benefit of the doubt. For zero length
  2790. // allocations, don't create free space, just insert.
  2791. //
  2792. } else if (BootAllocation->Length != 0) {
  2793. Status = IopArbiterAddFreeSpace(Arbiter,
  2794. BootAllocation->Allocation,
  2795. BootAllocation->Length,
  2796. 0,
  2797. NULL,
  2798. 0);
  2799. if (!KSUCCESS(Status)) {
  2800. goto ArbiterTryBootAllocationEnd;
  2801. }
  2802. ArbiterEntry = IopArbiterFindEntry(Arbiter,
  2803. BootAllocation->Allocation,
  2804. FALSE);
  2805. ASSERT(ArbiterEntry != NULL);
  2806. }
  2807. //
  2808. // Insert the boot allocation.
  2809. //
  2810. Status = IopArbiterInsertEntry(Arbiter,
  2811. ArbiterSpaceReserved,
  2812. Device,
  2813. BootAllocation->Allocation,
  2814. BootAllocation->Length,
  2815. BootAllocation->Characteristics,
  2816. Requirement->Flags | RESOURCE_FLAG_BOOT,
  2817. Requirement,
  2818. ArbiterEntry,
  2819. &NewEntry);
  2820. if (!KSUCCESS(Status)) {
  2821. goto ArbiterTryBootAllocationEnd;
  2822. }
  2823. //
  2824. // The space was successfully reserved, save it.
  2825. //
  2826. Context->Requirements[RequirementIndex].Allocation = NewEntry;
  2827. Status = STATUS_SUCCESS;
  2828. ArbiterTryBootAllocationEnd:
  2829. return Status;
  2830. }
  2831. PRESOURCE_ALLOCATION
  2832. IopArbiterFindBootAllocationForRequirement (
  2833. PDEVICE Device,
  2834. PRESOURCE_REQUIREMENT Requirement
  2835. )
  2836. /*++
  2837. Routine Description:
  2838. This routine attempts to find the boot resource allocation that matches
  2839. with the given device's resource requirement.
  2840. Arguments:
  2841. Device - Supplies a pointer to the device being queried.
  2842. Requirement - Supplies a pointer to the resource requirement whose boot
  2843. allocation counterpart should be found.
  2844. Return Value:
  2845. Returns a pointer to the boot time allocation that satisfies the given
  2846. requirement.
  2847. NULL if the allocation could not be found.
  2848. --*/
  2849. {
  2850. PRESOURCE_ALLOCATION Allocation;
  2851. PRESOURCE_ALLOCATION_LIST AllocationList;
  2852. PRESOURCE_REQUIREMENT CurrentRequirement;
  2853. PRESOURCE_REQUIREMENT_LIST RequirementList;
  2854. ULONG ResourceIndex;
  2855. //
  2856. // Only the first requirement list is searched.
  2857. //
  2858. RequirementList =
  2859. IoGetNextResourceConfiguration(Device->ResourceRequirements, NULL);
  2860. ASSERT(RequirementList != NULL);
  2861. //
  2862. // Determine the index of the given requirement in the list of requirements.
  2863. //
  2864. ResourceIndex = 0;
  2865. CurrentRequirement = IoGetNextResourceRequirement(RequirementList, NULL);
  2866. while (CurrentRequirement != NULL) {
  2867. if (CurrentRequirement == Requirement) {
  2868. break;
  2869. }
  2870. ResourceIndex += 1;
  2871. CurrentRequirement = IoGetNextResourceRequirement(RequirementList,
  2872. CurrentRequirement);
  2873. }
  2874. if (CurrentRequirement == NULL) {
  2875. return NULL;
  2876. }
  2877. //
  2878. // Now go that many entries into the boot allocation list.
  2879. //
  2880. AllocationList = Device->BootResources;
  2881. if (AllocationList == NULL) {
  2882. return NULL;
  2883. }
  2884. Allocation = IoGetNextResourceAllocation(AllocationList, NULL);
  2885. while ((ResourceIndex != 0) && (Allocation != NULL)) {
  2886. ResourceIndex -= 1;
  2887. Allocation = IoGetNextResourceAllocation(AllocationList, Allocation);
  2888. }
  2889. if (Allocation == NULL) {
  2890. return NULL;
  2891. }
  2892. //
  2893. // Throw it out if the types don't match. Other checking is not done
  2894. // because the allocation may satisfy an alternative instead of this exact
  2895. // requirement.
  2896. //
  2897. if (Allocation->Type != Requirement->Type) {
  2898. return NULL;
  2899. }
  2900. return Allocation;
  2901. }
  2902. VOID
  2903. IopArbiterClearContextAllocations (
  2904. PARBITER_ALLOCATION_CONTEXT Context
  2905. )
  2906. /*++
  2907. Routine Description:
  2908. This routine frees any reserved allocations made on behalf of the given
  2909. allocation context.
  2910. Arguments:
  2911. Context - Supplies a pointer to the context whose allocations should be
  2912. cleared and freed.
  2913. Return Value:
  2914. None.
  2915. --*/
  2916. {
  2917. PRESOURCE_ARBITER Arbiter;
  2918. PARBITER_ENTRY Entry;
  2919. PARBITER_ALLOCATION_REQUIREMENT RequirementData;
  2920. ULONG RequirementIndex;
  2921. for (RequirementIndex = 0;
  2922. RequirementIndex < Context->RequirementCount;
  2923. RequirementIndex += 1) {
  2924. RequirementData = &(Context->Requirements[RequirementIndex]);
  2925. Arbiter = IOP_ARBITER_GET_ARBITER(Context, RequirementData);
  2926. ASSERT(Arbiter != NULL);
  2927. Entry = RequirementData->Allocation;
  2928. if (Entry != NULL) {
  2929. IopArbiterFreeEntry(Arbiter, Entry);
  2930. }
  2931. RequirementData->Allocation = NULL;
  2932. }
  2933. return;
  2934. }
  2935. VOID
  2936. IopArbiterLinkContextAllocations (
  2937. PARBITER_ALLOCATION_CONTEXT Context
  2938. )
  2939. /*++
  2940. Routine Description:
  2941. This routine links each allocation made in an allocation context to its
  2942. corresponding requirement and device.
  2943. Arguments:
  2944. Context - Supplies a pointer to the context whose allocations should be
  2945. cleared and freed.
  2946. Return Value:
  2947. None.
  2948. --*/
  2949. {
  2950. PDEVICE AllocationDevice;
  2951. PARBITER_ENTRY Entry;
  2952. ULONG RequirementIndex;
  2953. for (RequirementIndex = 0;
  2954. RequirementIndex < Context->RequirementCount;
  2955. RequirementIndex += 1) {
  2956. Entry = Context->Requirements[RequirementIndex].Allocation;
  2957. if (Entry == NULL) {
  2958. continue;
  2959. }
  2960. AllocationDevice = Entry->Device;
  2961. INSERT_AFTER(&(Entry->ConfigurationListEntry),
  2962. &(AllocationDevice->ArbiterAllocationListHead));
  2963. }
  2964. return;
  2965. }
  2966. KSTATUS
  2967. IopDeferResourceAllocation (
  2968. PDEVICE Device
  2969. )
  2970. /*++
  2971. Routine Description:
  2972. This routine adds the given device to the array of devices whose resource
  2973. allocation is being deferred until after all devices with boot allocations
  2974. have been enumerated.
  2975. Arguments:
  2976. Device - Supplies a pointer to the device to add.
  2977. Return Value:
  2978. Status code.
  2979. --*/
  2980. {
  2981. PDEVICE *NewArray;
  2982. UINTN NewSize;
  2983. NewSize = IoDelayedDeviceCount + 1;
  2984. NewArray = MmAllocatePagedPool(NewSize * sizeof(PDEVICE),
  2985. ARBITER_ALLOCATION_TAG);
  2986. if (NewArray == NULL) {
  2987. return STATUS_INSUFFICIENT_RESOURCES;
  2988. }
  2989. if (IoDelayedDevices != NULL) {
  2990. RtlCopyMemory(NewArray,
  2991. IoDelayedDevices,
  2992. (NewSize - 1) * sizeof(PDEVICE));
  2993. MmFreePagedPool(IoDelayedDevices);
  2994. }
  2995. NewArray[NewSize - 1] = Device;
  2996. IoDelayedDevices = NewArray;
  2997. IoDelayedDeviceCount = NewSize;
  2998. return STATUS_SUCCESS;
  2999. }