1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2% Copyright (c) 2009, 2011, ETH Zurich. 3% All rights reserved. 4% 5% This file is distributed under the terms in the attached LICENSE file. 6% If you do not find this file, copies can be found by writing to: 7% ETH Zurich D-INFK, Haldeneggsteig 4, CH-8092 Zurich. Attn: Systems Group. 8%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 9 10:-lib(ic). 11:-lib(ic_global). 12:-use_module(library(ic_edge_finder)). 13 14:- set_flag(print_depth, 200). 15 16:-dynamic(currentbar/5). 17 18% :-include("../data/data_hand.txt"). 19% :-include("../data/data_qemu_hand.txt"). 20% :-include("../data/data_qemu.txt"). 21% :-include("../data/data_nos3.txt"). 22% :-include("../data/data_nos4.txt"). 23% :-include("../data/data_nos5.txt"). 24% :-include("../data/data_nos6.txt"). 25% :-include("../data/data_gruyere.txt"). 26% :-include("../data/data_sbrinz1.txt"). 27% :-include("../data/data_loner.txt"). 28 29 30 31%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 32% main goal to be called from outside 33%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 34 35bridge_programming(Plan, NrElements) :- 36 Granularity is 4096, 37% find all the root bridges 38 findall(root(Addr,Child,mem(LP,HP)), 39 ( rootbridge(Addr,Child,mem(L,H)), 40 LT1 is L / Granularity, 41 ceiling(LT1, LT2), 42 integer(LT2, LP), 43 HT1 is H / Granularity, 44 ceiling(HT1, HT2), 45 integer(HT2, HP) 46 ),Roots), 47% exclude fixed memory from being allocated to devices 48 ( is_predicate(fixed_memory/2) -> 49 findall(range(ResLowP,ResSizeP), 50 ( 51 fixed_memory(ResLow,ResHigh), T1 is ResLow / Granularity, floor(T1,T2), 52 integer(T2,ResLowP), 53 T3 is (ResHigh - ResLow) / Granularity, 54 ceiling(T3,T4), 55 integer(T4,ResSizeP) 56 ), ExclRangesFixed); 57 ExclRangesFixed = [] 58 ), 59% exclude IOAPIC regions from being allocated to devices 60 ( is_predicate(ioapic/3) -> 61 % according to the spec we need 64Bytes in the Intel case. Reserve a page 62 % anyway, since currently we cannot query the real requested size 63 TSz is (4096 / Granularity), 64 ceiling(TSz, TSz2), 65 integer(TSz2, IOAPIC_MinSize), 66 findall(range(Bs,IOAPIC_MinSize), 67 ( 68 ioapic(_,B,_), 69 T1 is B / Granularity, 70 floor(T1, T2), 71 integer(T2, Bs) 72 ),IOAPICs) 73 ; 74 IOAPICs = [] 75 ), 76 77%if IOAPIC appears as BAR, do not add this region to the "avoid" regions 78 findall(range(SubBase, SubSize), 79 ( 80 member(IOAPICRegionMember, IOAPICs), 81 range(SubBase, SubSize) = IOAPICRegionMember, 82 bar(_,_,OrigBarBase,_,_,_,_), 83 T27 is OrigBarBase / Granularity, 84 floor(T27, T28), 85 integer(T28, SubBase) 86 ), RemoveRegionList), 87 subtract(IOAPICs,RemoveRegionList,IOAPICsRemoveRegionList), 88 89%all the regions to avoid 90 append(ExclRangesFixed, IOAPICsRemoveRegionList, ExclRanges), 91 92% create an assignment for all PCI buses (all root bridges and their children) 93 ( foreach(Root,Roots), 94 foreach(P,Plan), 95 foreach(L,Lengths), 96 param(Granularity), 97 param(ExclRanges), 98 param(IOAPICs) 99 do 100 bridge_assignment(P,Root, Granularity, ExclRanges, IOAPICs), 101 length(P,L) 102 ), 103 sum(Lengths,NrElements). 104 105 106%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 107% small tools 108%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 109 110adjust_range(X, buselement(T,A,Sec,B1,H1,S,Tp,PF, PCIe, Bits), buselement(T,A,Sec,B2,H2,S,Tp,PF, PCIe, Bits)) :- 111 B2 is B1 + X, 112 H2 is H1 + X. 113 114back_to_bytes(Granularity, buselement(T,A,Sec,BP,HP,SP,Tp,PF, PCIe, Bits), buselement(T,A,Sec,B,H,S,Tp,PF, PCIe, Bits)) :- 115 B is BP * Granularity, 116 H is HP * Granularity, 117 S is SP * Granularity. 118 119 120%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 121% the main part of the allocation. Called once per root bridge 122%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 123 124bridge_assignment(Plan, Root, Granularity, ExclRanges, IOAPICs) :- 125 root(Addr,childbus(MinBus,MaxBus),mem(LMem,HMem)) = Root, 126 X is HMem - LMem, 127 Type = mem, 128 129% prefetchable 130 constrain_bus(Granularity, Type, prefetchable, Addr,MinBus,MaxBus,LMem,HMem,BusElementListP), 131 RBaseP::[LMem..HMem], 132 RHighP::[LMem..HMem], 133 RSizeP::[0..X], 134 devicetree(BusElementListP,buselement(bridge,Addr,secondary(MinBus),RBaseP,RHighP,RSizeP, Type, prefetchable, _, _),TP), 135 136% nonprefetchable 137 constrain_bus(Granularity, Type, nonprefetchable, Addr,MinBus,MaxBus,LMem,HMem,BusElementListNP), 138 RBaseNP::[LMem..HMem], 139 RHighNP::[LMem..HMem], 140 RSizeNP::[0..X], 141 devicetree(BusElementListNP,buselement(bridge,Addr,secondary(MinBus),RBaseNP,RHighNP,RSizeNP, Type, nonprefetchable, _, _),TNP), 142 143% pseudo-root of both trees 144 PseudoBase::[LMem..HMem], 145 PseudoHigh::[LMem..HMem], 146 PseudoSize::[0..X], 147 T = t(buselement(bridge, addr(-1, -1, -1), childbus(-1, -1), PseudoBase, PseudoHigh, PseudoSize, _, _, _, _), [TP, TNP]), 148 setrange(T,_,_,_), 149 nonoverlap(T), 150 naturally_aligned(T, 256, LMem, HMem), 151 tree2list(T,ListaU), 152 sort(6, >=, ListaU, Lista), 153 not_overlap_memory_ranges(Lista, ExclRanges), 154 keep_orig_addr(Lista, 12, 3, _, _, _, _), 155 keep_ioapic_bars(Lista, IOAPICs), 156 labelall(Lista), 157 subtract(Lista,[buselement(bridge,Addr,_,_,_,_,_,prefetchable,_,_)],Pl3), 158 subtract(Pl3,[buselement(bridge,Addr,_,_,_,_,_,nonprefetchable,_,_)],Pl2), 159 subtract(Pl2,[buselement(bridge,addr(-1,-1,-1),_,_,_,_,_,_,_,_)],Pl), 160 maplist(adjust_range(0),Pl,PR), 161 maplist(back_to_bytes(Granularity),PR,Plan). 162 163% dot output: 164% PrBaseBytePref is RBaseP * Granularity, 165% PrHighBytePref is RHighP * Granularity, 166% PrBaseByteNonPref is RBaseNP * Granularity, 167% PrHighByteNonPref is RHighNP * Granularity, 168% plan_to_dot(Granularity, Plan, Root, PrBaseBytePref, PrHighBytePref, PrBaseByteNonPref, PrHighByteNonPref). 169 170 171%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 172% instantiating the variables 173%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 174 175base(buselement(_,_,_,Base,_,_,_,_,_,_),Base). 176high(buselement(_,_,_,_,High,_,_,_,_,_),High). 177size(buselement(_,_,_,_,_,Size,_,_,_,_),Size). 178 179labelall(BusElementList) :- 180 maplist(base, BusElementList, Base), 181 maplist(high, BusElementList, High), 182 maplist(size, BusElementList, Size), 183 append(Base, High, L1), 184 append(L1, Size, L2), 185 labeling(L2). 186 187 188 189%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 190% create the list of devices and bridges in form of buselements and create the 191% variables. 192% we care about the allocation of memory mapped registers here, therefore we only 193% look at bar located in "mem", not "io" 194%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 195 196constrain_bus(Granularity, Type, Prefetch, RootAddr,Bus,MaxBus,LMem,HMem,OutBusElementList) :- 197 constrain_bus_ex(Granularity, Type, Prefetch, RootAddr,Bus,MaxBus,LMem,HMem,[],OutBusElementList). 198 199constrain_bus_ex(_, _, _, _,Bus,MaxBus,_,_,InL,InL) :- Bus > MaxBus. 200constrain_bus_ex(Granularity, Type, Prefetch, RootAddr,Bus,MaxBus,LMem,HMem,InBusElementList,OutBusElementList) :- 201 Bus =< MaxBus, 202 SMax is HMem - LMem, 203 ( is_predicate(bridge/8) -> 204 findall(buselement(bridge,addr(Bus,Dev,Fun),secondary(Sec),Base,High,Size,Type,Prefetch, PCIe, 0), 205 ( bridge(PCIe, addr(Bus,Dev,Fun), _, _, _, _, _, secondary(Sec)), 206 not addr(Bus,Dev,Fun) = RootAddr, 207 Base::[LMem..HMem],High::[LMem..HMem],Size::[0..SMax] 208 ),BridgeList); 209 BridgeList = [] 210 ), 211 ( is_predicate(device/8) -> 212 findall(buselement(device,addr(Bus,Dev,Fun),BAR,Base,High,SizeP,Type,Prefetch, PCIe, Bits), 213 ( device(PCIe, addr(Bus,Dev,Fun),_,_,_,_,_,_), 214 bar(addr(Bus,Dev,Fun),BAR,_,Size, Type, Prefetch, Bits), 215 Base::[LMem..HMem],High::[LMem..HMem], 216 ST1 is Size / Granularity, 217 ceiling(ST1, ST2), 218 integer(ST2, SizeP) 219 ),DeviceList); 220 DeviceList = [] 221 ), 222 append(BridgeList, DeviceList, MyBusElementList), 223 append(InBusElementList, MyBusElementList, NewBusElementList), 224 NextBus is Bus + 1, 225 constrain_bus_ex(Granularity, Type, Prefetch, RootAddr, NextBus, MaxBus, LMem,HMem,NewBusElementList,OutBusElementList). 226 227 228%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 229% create the PCI(e) device tree from a list of "buselement" and return it in Tree 230%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 231 232devicetree(List,CurrRoot,Tree) :- 233 buselement(bridge,_,secondary(Sec),_,_,_,_,_,_,_) = CurrRoot, 234 findall(X,( 235 member(Y,List), 236 buselement(_,addr(Sec,_,_),_,_,_,_,_,_,_,_) = Y, 237 devicetree(List, Y, X)),Children 238 ), 239 Tree = t(CurrRoot,Children). 240devicetree(_,CurrRoot,Tree) :- 241 buselement(device,_,_,_,_,_,_,_,_,_) = CurrRoot, 242 Tree = t(CurrRoot, []). 243 244 245%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 246% convert a tree to a list of buselements 247%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 248 249tree2list([],[]). 250tree2list(Tree, List) :- 251 t(Node,Children) = Tree, 252 ( foreach(El,Children), 253 foreach(L1,ChildList) 254 do 255 tree2list(El,L1) 256 ), 257 flatten(ChildList,L2), 258 List = [Node|L2]. 259 260 261 262%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 263% store the new values of the BARs 264%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 265replace_current_BAR_values(L) :- 266 delete_current_BAR_values(L), 267 store_current_BAR_values(L). 268 269store_current_BAR_values([]). 270store_current_BAR_values([H|T]) :- 271 ( buselement(device,Addr,BAR,Base,High,Size,_,_,_,_) = H -> 272 assert(currentbar(Addr,BAR,Base,High,Size)); 273 true 274 ), 275 store_current_BAR_values(T). 276 277 278delete_current_BAR_values([]). 279delete_current_BAR_values([H|T]) :- 280 ( buselement(device,Addr,BAR,_,_,_,_,_,_,_) = H -> 281 ( currentbar(Addr,BAR,_,_,_) -> 282 retract(currentbar(Addr,BAR,_,_,_)); 283 true 284 ); 285 true 286 ), 287 delete_current_BAR_values(T). 288 289 290 291 292%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 293% add constraints to the tree 294%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 295 296% make sure that the bridge has a range which includes all the children 297setrange(Tree,SubTreeSize,SubTreeMin,SubTreeMax) :- 298 t(Node,Children) = Tree, 299 ( foreach(El,Children), 300 foreach(Sz,SizeList), 301 foreach(Mi,MinList), 302 foreach(Ma,MaxList) 303 do 304 setrange(El,Sz,Mi,Ma) 305 ), 306 ic_global:sumlist(SizeList,Size), 307 buselement(_,_,_,Base,High,ElemSize,_,_,_,_) = Node, 308 ElemSize $>= Size, 309 ( not MinList=[] -> 310 ic:minlist(MinList,Min), 311 ic:maxlist(MaxList,Max), 312 Min $>= Base, 313 Max $=< High; 314 true 315 ), 316 High $= Base + ElemSize, 317 SubTreeSize $= ElemSize, 318 SubTreeMin $= Base, 319 SubTreeMax $= High. 320setrange([],0,_,_). 321 322 323% make sure that the children do not overlap 324child(t(C,_),C). 325nonoverlap(Tree) :- 326 t(_ ,Children) = Tree, 327 maplist(child,Children,ChildList), 328 ( not ChildList=[] -> 329 maplist(base,ChildList,Base), 330 maplist(size,ChildList,Size), 331 disjunctive(Base,Size); 332 true 333 ), 334 ( foreach(El, Children) 335 do 336 nonoverlap(El) 337 ). 338 339 340naturally_aligned(Tree, BridgeAlignment, LMem, HMem) :- 341 t(Node,Children) = Tree, 342 ( buselement(device,_,_,Base,High,Size,_,_,_,_) = Node -> 343 Divisor is Size 344 ; 345 buselement(bridge,_,_,Base,High,_,_,_,_,_) = Node -> 346 Divisor is BridgeAlignment 347 ), 348 349 T1 is (HMem - LMem) / Divisor, 350 ceiling(T1, T2), 351 integer(T2, Nr), 352 N::[0..Nr], 353 N2::[0..Nr], 354 mod(LMem,Divisor,Remainder), 355 ( Remainder =:= 0 -> 356 Corr is 0; 357 Corr is Divisor - Remainder 358 ), 359 Base $= N*Divisor + LMem + Corr, 360 High $>= Base, 361 High $= N2*Divisor + LMem + Corr, 362 ( foreach(El, Children), 363 param(BridgeAlignment), 364 param(LMem), 365 param(HMem) 366 do 367 naturally_aligned(El, BridgeAlignment, LMem, HMem) 368 ). 369 370 371% do not overlap with the given list of memory ranges 372not_overlap_memory_ranges([], _). 373not_overlap_memory_ranges(_, []). 374not_overlap_memory_ranges([buselement(bridge,_,_,_,_,_,_,_,_,_)|PCIList], MemoryRanges) :- 375 not_overlap_memory_ranges(PCIList, MemoryRanges). 376not_overlap_memory_ranges([H|PCIList], MemoryRanges) :- 377 ( foreach(range(RBase,RSize),MemoryRanges), 378 param(H) 379 do 380 buselement(device,_,_,Base,_,Size,_,_,_,_) = H, 381 append([Base],[RBase],Bases), 382 append([Size],[RSize],Sizes), 383 disjunctive(Bases,Sizes) 384 ), 385 not_overlap_memory_ranges(PCIList, MemoryRanges). 386 387 388keep_orig_addr([], _, _, _, _, _, _). 389keep_orig_addr([H|Buselements], Class, SubClass, ProgIf, Bus, Dev, Fun) :- 390 ( buselement(device,addr(Bus,Dev,Fun),BAR,Base,_,_,_,_,_,_) = H,device(_,addr(Bus,Dev,Fun),_,_,Class, SubClass, ProgIf,_),bar(addr(Bus,Dev,Fun),BAR,OrigBase,_,_,_,_) -> 391 T1 is OrigBase / 4096, 392 floor(T1,T2), 393 integer(T2,KeepBase), 394 Base $= KeepBase; 395 true 396 ), 397 keep_orig_addr(Buselements, Class, SubClass, ProgIf, Bus, Dev, Fun). 398 399% on some machines (sbrinz1) one of the two IOAPICs appears as a BAR 400% on a device which claims to be a RAM memory controller. If this occurs, 401% we want to avoid moving this BAR as otherwise the IOAPIC cannot be reached 402% anymore. 403keep_ioapic_bars(_, []). 404keep_ioapic_bars(Buselements, [H|IOAPICList]) :- 405 ( 406 range(B, _) = H, 407 bar(addr(Bus,Dev,Fun),_,OrigBase,_,_,_,_), 408 T1 is OrigBase / 4096, 409 floor(T1,T2), 410 integer(T2,KeepBase), 411 KeepBase =:= B -> 412 keep_orig_addr(Buselements, _, _, _, Bus, Dev, Fun); 413 true 414 ), 415 keep_ioapic_bars(Buselements, IOAPICList). 416