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% the PCI tree is constructed by adding child devices to the bridge. all the 11% children are sorted by the requesting size of the children in descending order. 12% on the next level children (which include subordinate bridges) are sorted by 13% the biggest requesting child (not the sum of the children under a bridge). 14% the bridges Sz variable contains therefore the size of the biggest requesting 15% child, not the size under the bridge. like this, we can allocate resources 16% for the biggest requesting child first. 17 18 19%:-dynamic(bridge/8). 20%:-dynamic(bar/7). 21 22% :-include("../data/data_nos6.txt"). 23% :-include("../data/data_qemu_hand.txt"). 24% :-include("../data/data_qemu.txt"). 25% :-include("../data/data_nos4.txt"). 26% :-include("../data/data_nos5.txt"). 27% :-include("../data/data_hand.txt"). 28 29% asq: important: this entry _has_ to be here all the time!! 30% bridge(pcie, addr(0,0,0),0,0,6,4,0,secondary(0)). 31bar(addr(0,0,0),0,0,5,mem, nonprefetchable,0). 32bar(addr(0,0,0),0,0,5,mem, prefetchable,0). 33 34:- set_flag(print_depth, 200). 35 36 37%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 38% main goal to be called from outside 39%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 40 41bridge_programming(Plan, NrElements) :- 42 43 Granularity is 4096, 44 FixedAddresses=[fixed(12,3,_)], 45 reserve_fixed_addresses(FixedAddresses), 46 47 findall(root(Addr,Child,mem(LP,HP)), 48 ( rootbridge(Addr,Child,mem(L,H)), 49 LT1 is L / Granularity, 50 ceiling(LT1, LT2), 51 integer(LT2, LP), 52 HT1 is H / Granularity, 53 ceiling(HT1, HT2), 54 integer(HT2, HP) 55 ),Roots), 56 ( is_predicate(fixed_memory/2) -> 57 findall(range(ResLowP,ResSizeP), 58 ( 59 fixed_memory(ResLow,ResHigh), T1 is ResLow / Granularity, floor(T1,T2), 60 integer(T2,ResLowP), 61 T3 is (ResHigh - ResLow) / Granularity, 62 ceiling(T3,T4), 63 integer(T4,ResSizeP) 64 ), ExclRanges); 65 ExclRanges = [] 66 ), 67 ( foreach(Root,Roots), 68 foreach(P,Plan), 69 foreach(L,Lengths), 70 param(Granularity), 71 param(ExclRanges), 72 param(FixedAddresses) 73 do 74 bridge_assignment(P,Root, Granularity, ExclRanges, FixedAddresses), 75 length(P,L) 76 ), 77 sum(Lengths,NrElements). 78 79 80 81 82 83 84%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 85% construct a tree and do the assignment 86%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 87 88bridge_assignment(Plan, Root, Granularity, ExclRanges, FixedAddresses) :- 89 root(Addr,childbus(MinBus,MaxBus),mem(LMem,HMem)) = Root, 90 X is HMem - LMem, 91 Type = mem, 92% prefetchable and nonprefetchable 93 constrain_bus(Granularity, Type, _, Addr,MinBus,MaxBus,LMem,HMem,BusElementListP), 94 devicetree(BusElementListP,buselement(bridge,Addr,secondary(MinBus),RBaseP,RHighP,RSizeP, Type, _, _, _),T), 95 96% prefetchable 97% constrain_bus(Granularity, Type, prefetchable, Addr,MinBus,MaxBus,LMem,HMem,BusElementListP), 98% devicetree(BusElementListP,buselement(bridge,Addr,secondary(MinBus),RBaseP,RHighP,RSizeP, Type, prefetchable, _, _),TP), 99 100%% nonprefetchable 101% constrain_bus(Granularity, Type, nonprefetchable, Addr,MinBus,MaxBus,LMem,HMem,BusElementListNP), 102% devicetree(BusElementListNP,buselement(bridge,Addr,secondary(MinBus),RBaseNP,RHighNP,RSizeNP, Type, nonprefetchable, _, _),TNP), 103 104%% pseudo-root of both trees 105%% sorted 106% T = t(buselement(bridge, addr(-1, -1, -1), childbus(-1, -1), PseudoBase, PseudoHigh, PseudoSize, _, _, _, _), Sz, [TP, TNP]), 107% 108%% unsorted 109%% T = t(buselement(bridge, addr(-1, -1, -1), childbus(-1, -1), PseudoBase, PseudoHigh, PseudoSize, _, _, _, _), [TP, TNP]), 110 111 nl,nl,nl,writeln(tree),nl,writeln(T),nl,nl,nl, 112 pci_postorder(T, LMem, High, Granularity, FixedAddresses), 113 114% XXX 115% High =< HMem, 116 117 tree2list(T,Lista), 118 119 subtract(Lista,[buselement(bridge,Addr,_,_,_,_,_,_,_,_)],Pl), 120 compute_bridge_size(Pl), 121 maplist(adjust_range(0),Pl,PR), 122 maplist(back_to_bytes(Granularity),PR,Plan). 123 124% subtract(Lista,[buselement(bridge,Addr,_,_,_,_,_,prefetchable,_,_)],Pl3), 125% subtract(Pl3,[buselement(bridge,Addr,_,_,_,_,_,nonprefetchable,_,_)],Pl2), 126% subtract(Pl2,[buselement(bridge,addr(-1,-1,-1),_,_,_,_,_,_,_,_)],Pl), 127% maplist(adjust_range(0),Pl,PR), 128% maplist(back_to_bytes(Granularity),PR,Plan). 129 130 131%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 132% create the list of devices and bridges in form of buselements and create the 133% variables. 134% we care about the allocation of memory mapped registers here, therefore we only 135% look at bar located in "mem", not "io" 136%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 137 138constrain_bus(_, _, _, _,Bus,MaxBus,_,_,[]) :- Bus > MaxBus. 139constrain_bus(Granularity, Type, Prefetch, RootAddr,Bus,MaxBus,LMem,HMem,NewBusElementList) :- 140 Bus =< MaxBus, 141 SMax is HMem - LMem, 142 findall(buselement(bridge,addr(Bus,Dev,Fun),secondary(Sec),Base,High,Size,Type,Prefetch, PCIe, 0), 143 ( bridge(PCIe, addr(Bus,Dev,Fun), _, _, _, _, _, secondary(Sec)), 144 not addr(Bus,Dev,Fun) = RootAddr 145 ),BridgeList), 146 findall(buselement(device,addr(Bus,Dev,Fun),BAR,Base,High,SizeP,Type,Prefetch, PCIe, Bits), 147 ( device(PCIe, addr(Bus,Dev,Fun),_,_,_,_,_,_), 148 bar(addr(Bus,Dev,Fun),BAR,_,Size, Type, Prefetch, Bits), 149 ST1 is Size / Granularity, 150 ceiling(ST1, ST2), 151 integer(ST2, SizeP) 152 ),DeviceList), 153 append(BridgeList, DeviceList, BusElementList), 154 NextBus is Bus + 1, 155 constrain_bus(Granularity, Type, Prefetch, RootAddr, NextBus, MaxBus, LMem,HMem,List), 156 append(List,BusElementList,NewBusElementList). 157 158 159 160 161%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 162% create the PCI(e) device tree from a list of "buselement" and return it in Tree 163%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 164 165% sorted 166 167devicetree(List,CurrRoot,Tree) :- 168 buselement(bridge,_,secondary(Sec),_,_,_,_,_,_,_) = CurrRoot, 169 findall(X,( 170 member(Y,List), 171 buselement(_,addr(Sec,_,_),_,_,_,_,_,_,_,_) = Y, 172 devicetree(List, Y, X)),Children 173 ), 174 ( not Children=[] -> 175 sort(2, >=, Children, [H|ChildrenSorted]), 176 t(_,Sz,_) = H, 177 Tree = t(CurrRoot,Sz,[H|ChildrenSorted]); 178 Tree = t(CurrRoot,0,[]) 179 ). 180devicetree(_,CurrRoot,Tree) :- 181 buselement(device,_,_,_,_,Size,_,_,_,_) = CurrRoot, 182 Tree = t(CurrRoot, Size, []). 183 184 185 186% unsorted 187% 188%devicetree(List,CurrRoot,Tree) :- 189% buselement(bridge,_,secondary(Sec),_,_,_,_,_,_,_) = CurrRoot, 190% findall(X,( 191% member(Y,List), 192% buselement(_,addr(Sec,_,_),_,_,_,_,_,_,_,_) = Y, 193% devicetree(List, Y, X)),Children 194% ), 195% Tree = t(CurrRoot,Children). 196%devicetree(_,CurrRoot,Tree) :- 197% buselement(device,_,_,_,_,_,_,_,_,_) = CurrRoot, 198% Tree = t(CurrRoot, []). 199 200 201%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 202% convert a tree to a list of buselements 203%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 204 205% sorted 206tree2list([],[]). 207tree2list(Tree, List) :- 208 t(Node,_,Children) = Tree, 209 ( foreach(El,Children), 210 foreach(L1,ChildList) 211 do 212 tree2list(El,L1) 213 ), 214 flatten(ChildList,L2), 215 List = [Node|L2]. 216 217% unsorted 218%tree2list([],[]). 219%tree2list(Tree, List) :- 220% t(Node,Children) = Tree, 221% ( foreach(El,Children), 222% foreach(L1,ChildList) 223% do 224% tree2list(El,L1) 225% ), 226% flatten(ChildList,L2), 227% List = [Node|L2]. 228 229 230%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 231% Traverse tree in postoder mode and assign addresses to the devices 232%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 233 234pci_postorder([], StartAddr, StartAddr, _, _) :- writeln([]). 235pci_postorder(T, StartAddr, NextAddr, Granularity, FixedAddresses) :- 236 t(Node, _, Children) = T, 237 buselement(Type,Addr,BAR,Base,High,Size,_,_,_,_) = Node, 238 MBF is ((1024 * 1024) / Granularity), 239 integer(MBF, MB), 240 241% adjust the start address in case it is a device to avoid resource conflicts 242 adjust_start_address(Type, StartAddr, Size, Granularity, AllocationStartAddr), 243 244% now do the allocation 245 ( Type = device -> 246 mod(AllocationStartAddr, Size, Remainder), 247 ( Remainder > 0 -> 248 Base is AllocationStartAddr + Size - Remainder; 249 Base is AllocationStartAddr 250 ); 251 mod(AllocationStartAddr, MB, Remainder2), 252 ( Remainder2 > 0 -> 253 Base is AllocationStartAddr + MB - Remainder2; 254 Base is AllocationStartAddr 255 ) 256 ), 257 258 pci_postorder_children(Children, Base, NextChildAddr, Granularity, FixedAddresses), 259 260 ( Type = device -> 261 NextAddr is NextChildAddr + Size; 262 mod(NextChildAddr, MB, Remainder3), 263 ( Remainder3 > 0 -> 264 NextAddr is NextChildAddr + MB - Remainder3; 265 NextAddr is NextChildAddr 266 ) 267 ), 268 269 High = NextAddr, 270 writeln(Node), 271 writeln(NextChildAddr), 272 writeln(NextAddr). 273 274 275pci_postorder_children([], StartAddr, StartAddr, _, _). 276pci_postorder_children([H|T], StartAddr, NextAddr, Granularity, FixedAddresses) :- 277 pci_postorder(H, StartAddr, Next, Granularity, FixedAddresses), 278 pci_postorder_children(T, Next, NextAddr, Granularity, FixedAddresses). 279 280 281 282reserve_fixed_addresses([]). 283reserve_fixed_addresses([fixed(Class,SubClass,ProgIf)|T]) :- 284 findall(m(B,H), ( 285 device(_,Addr,_,_,Class, SubClass, ProgIf,_),bar(Addr,BAR,B,H,_,_,_) 286 ), 287 FixedList), 288 ( foreach(m(B,H),FixedList) 289 do 290 assert(fixed_memory(B,H)) 291 ), 292 reserve_fixed_addresses(T). 293 294 295 296 297 298%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 299% adjust startaddress: leave reserved regions and fixed addresses of devices out 300%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 301adjust_start_address(bridge, StartAddr, _, _, StartAddr). 302 303adjust_start_address(device, StartAddr, Size, Granularity, AllocStartAddr) :- 304 EndAddr is StartAddr + Size, 305 ( is_predicate(fixed_memory/2) -> 306 findall(r(B,H), ( 307 fixed_memory(ResLow,ResHigh), 308 T1 is ResLow / Granularity, 309 floor(T1,T2), 310 integer(T2,B), 311 T3 is ResHigh / Granularity, 312 ceiling(T3, T4), 313 integer(T4, H) 314 ), 315 ReservedList) 316 ; 317 ReservedList=[] 318 ), 319 320 IOAPIC_SizeT1 is (4096 / Granularity), 321 ceiling(IOAPIC_SizeT1, IOAPIC_SizeT2), 322 integer(IOAPIC_SizeT2, IOAPIC_Size), 323 findall(r(IOB,IOH),( 324 ioapic(_,B,_), 325 T1 is B / Granularity, 326 floor(T1, T2), 327 integer(T2, IOB), 328 IOH is IOB + IOAPIC_Size 329 ),IOAPIC_reserved), 330 append(ReservedList, IOAPIC_reserved, ResList), 331 ( foreach(r(B,H), ResList), 332 foreach(A, ConflictList), 333 param(StartAddr), 334 param(EndAddr) 335 do 336 ( StartAddr >= B, StartAddr =< H -> 337 A = H; 338 EndAddr >= B, EndAddr =< H -> 339 A = H; 340 StartAddr =< B, EndAddr >= H -> 341 A = H; 342 A = 0 343 ) 344 ), 345 max(ConflictList,Max), 346 max([Max,StartAddr], AllocStartAddrAdjusted), 347 348 mod(AllocStartAddrAdjusted, Size, Remainder), 349 ( Remainder > 0 -> 350 AllocStartAddr is AllocStartAddrAdjusted + Size - Remainder; 351 AllocStartAddr is AllocStartAddrAdjusted 352 ). 353 354 355 356 357%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 358% tools 359%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 360 361adjust_range(X, buselement(T,A,Sec,B1,H1,S,Tp,PF, PCIe, Bits), buselement(T,A,Sec,B2,H2,S,Tp,PF, PCIe, Bits)) :- 362 B2 is B1 + X, 363 H2 is H1 + X. 364 365back_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)) :- 366 B is BP * Granularity, 367 H is HP * Granularity, 368 S is SP * Granularity. 369 370base(buselement(_,_,_,Base,_,_,_,_,_,_),Base). 371high(buselement(_,_,_,_,High,_,_,_,_,_),High). 372size(buselement(_,_,_,_,_,Size,_,_,_,_),Size). 373 374 375compute_bridge_size([]). 376compute_bridge_size([buselement(device,_,_,_,_,_,_,_,_,_)|T]) :- 377 compute_bridge_size(T). 378compute_bridge_size([buselement(bridge,_,_,Base,High,Size,_,_,_,_)|T]) :- 379 Size is High - Base, 380 compute_bridge_size(T). 381 382 383%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 384% store the new values of the BARs 385%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 386replace_current_BAR_values(L) :- 387 delete_current_BAR_values(L), 388 store_current_BAR_values(L). 389 390store_current_BAR_values([]). 391store_current_BAR_values([H|T]) :- 392 ( buselement(device,Addr,BAR,Base,High,Size,_,_,_,_) = H -> 393 assert(currentbar(Addr,BAR,Base,High,Size)); 394 true 395 ), 396 store_current_BAR_values(T). 397 398 399delete_current_BAR_values([]). 400delete_current_BAR_values([H|T]) :- 401 ( buselement(device,Addr,BAR,_,_,_,_,_,_,_) = H -> 402 ( currentbar(Addr,BAR,_,_,_) -> 403 retract(currentbar(Addr,BAR,_,_,_)); 404 true 405 ); 406 true 407 ), 408 delete_current_BAR_values(T). 409 410 411 412