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 93% prefetchable and nonprefetchable 94 constrain_bus(Granularity, Type, _, Addr,MinBus,MaxBus,LMem,HMem,BusElementListP), 95 devicetree(BusElementListP,buselement(bridge,Addr,secondary(MinBus),RBaseP,RHighP,RSizeP, Type, _, _, _),T), 96 97% prefetchable 98% constrain_bus(Granularity, Type, prefetchable, Addr,MinBus,MaxBus,LMem,HMem,BusElementListP), 99% devicetree(BusElementListP,buselement(bridge,Addr,secondary(MinBus),RBaseP,RHighP,RSizeP, Type, prefetchable, _, _),TP), 100 101%% nonprefetchable 102% constrain_bus(Granularity, Type, nonprefetchable, Addr,MinBus,MaxBus,LMem,HMem,BusElementListNP), 103% devicetree(BusElementListNP,buselement(bridge,Addr,secondary(MinBus),RBaseNP,RHighNP,RSizeNP, Type, nonprefetchable, _, _),TNP), 104 105%% pseudo-root of both trees 106%% sorted 107% T = t(buselement(bridge, addr(-1, -1, -1), childbus(-1, -1), PseudoBase, PseudoHigh, PseudoSize, _, _, _, _), Sz, [TP, TNP]), 108% 109%% unsorted 110%% T = t(buselement(bridge, addr(-1, -1, -1), childbus(-1, -1), PseudoBase, PseudoHigh, PseudoSize, _, _, _, _), [TP, TNP]), 111 112 nl,nl,nl,writeln(tree),nl,writeln(T),nl,nl,nl, 113 pci_postorder(T, LMem, High, Granularity), 114 115% XXX 116% High =< HMem, 117 118 tree2list(T,Lista), 119 120 subtract(Lista,[buselement(bridge,Addr,_,_,_,_,_,_,_,_)],Pl), 121 compute_bridge_size(Pl), 122 maplist(adjust_range(0),Pl,PR), 123 maplist(back_to_bytes(Granularity),PR,Plan). 124 125% subtract(Lista,[buselement(bridge,Addr,_,_,_,_,_,prefetchable,_,_)],Pl3), 126% subtract(Pl3,[buselement(bridge,Addr,_,_,_,_,_,nonprefetchable,_,_)],Pl2), 127% subtract(Pl2,[buselement(bridge,addr(-1,-1,-1),_,_,_,_,_,_,_,_)],Pl), 128% maplist(adjust_range(0),Pl,PR), 129% maplist(back_to_bytes(Granularity),PR,Plan). 130 131 132%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 133% create the list of devices and bridges in form of buselements and create the 134% variables. 135% we care about the allocation of memory mapped registers here, therefore we only 136% look at bar located in "mem", not "io" 137%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 138 139constrain_bus(_, _, _, _,Bus,MaxBus,_,_,[]) :- Bus > MaxBus. 140constrain_bus(Granularity, Type, Prefetch, RootAddr,Bus,MaxBus,LMem,HMem,NewBusElementList) :- 141 Bus =< MaxBus, 142 SMax is HMem - LMem, 143 findall(buselement(bridge,addr(Bus,Dev,Fun),secondary(Sec),Base,High,Size,Type,Prefetch, PCIe, 0), 144 ( bridge(PCIe, addr(Bus,Dev,Fun), _, _, _, _, _, secondary(Sec)), 145 not addr(Bus,Dev,Fun) = RootAddr 146 ),BridgeList), 147 findall(buselement(device,addr(Bus,Dev,Fun),BAR,Base,High,SizeP,Type,Prefetch, PCIe, Bits), 148 ( device(PCIe, addr(Bus,Dev,Fun),_,_,_,_,_,_), 149 bar(addr(Bus,Dev,Fun),BAR,_,Size, Type, Prefetch, Bits), 150 ST1 is Size / Granularity, 151 ceiling(ST1, ST2), 152 integer(ST2, SizeP) 153 ),DeviceList), 154 append(BridgeList, DeviceList, BusElementList), 155 NextBus is Bus + 1, 156 constrain_bus(Granularity, Type, Prefetch, RootAddr, NextBus, MaxBus, LMem,HMem,List), 157 append(List,BusElementList,NewBusElementList). 158 159 160 161 162%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 163% create the PCI(e) device tree from a list of "buselement" and return it in Tree 164%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 165 166% sorted 167 168devicetree(List,CurrRoot,Tree) :- 169 buselement(bridge,_,secondary(Sec),_,_,_,_,_,_,_) = CurrRoot, 170 findall(X,( 171 member(Y,List), 172 buselement(_,addr(Sec,_,_),_,_,_,_,_,_,_,_) = Y, 173 devicetree(List, Y, X)),Children 174 ), 175 ( not Children=[] -> 176 sort(2, =<, Children, [H|ChildrenSorted]), 177 t(_,Sz,_) = H, 178 Tree = t(CurrRoot,Sz,[H|ChildrenSorted]); 179 Tree = t(CurrRoot,9,[]) 180 ). 181devicetree(_,CurrRoot,Tree) :- 182 buselement(device,_,_,_,_,Size,_,_,_,_) = CurrRoot, 183 Tree = t(CurrRoot, Size, []). 184 185 186 187% unsorted 188% 189%devicetree(List,CurrRoot,Tree) :- 190% buselement(bridge,_,secondary(Sec),_,_,_,_,_,_,_) = CurrRoot, 191% findall(X,( 192% member(Y,List), 193% buselement(_,addr(Sec,_,_),_,_,_,_,_,_,_,_) = Y, 194% devicetree(List, Y, X)),Children 195% ), 196% Tree = t(CurrRoot,Children). 197%devicetree(_,CurrRoot,Tree) :- 198% buselement(device,_,_,_,_,_,_,_,_,_) = CurrRoot, 199% Tree = t(CurrRoot, []). 200 201 202%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 203% convert a tree to a list of buselements 204%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 205 206% sorted 207tree2list([],[]). 208tree2list(Tree, List) :- 209 t(Node,_,Children) = Tree, 210 ( foreach(El,Children), 211 foreach(L1,ChildList) 212 do 213 tree2list(El,L1) 214 ), 215 flatten(ChildList,L2), 216 List = [Node|L2]. 217 218% unsorted 219%tree2list([],[]). 220%tree2list(Tree, List) :- 221% t(Node,Children) = Tree, 222% ( foreach(El,Children), 223% foreach(L1,ChildList) 224% do 225% tree2list(El,L1) 226% ), 227% flatten(ChildList,L2), 228% List = [Node|L2]. 229 230 231%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 232% Traverse tree in postoder mode and assign addresses to the devices 233%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 234 235pci_postorder([], StartAddr, StartAddr, _) :- writeln([]). 236pci_postorder(T, StartAddr, NextAddr, Granularity) :- 237 t(Node, _, Children) = T, 238 buselement(Type,_,_,Base,High,Size,_,_,_,_) = Node, 239 MBF is ((1024 * 1024) / Granularity), 240 integer(MBF, MB), 241 242% adjust the start address in case it is a device to avoid resource conflicts 243 adjust_start_address(Type, StartAddr, Size, Granularity, AllocationStartAddr), 244 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), 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 High = NextAddr, 269 writeln(Node), 270 writeln(NextChildAddr), 271 writeln(NextAddr). 272 273pci_postorder_children([], StartAddr, StartAddr, _). 274pci_postorder_children([H|T], StartAddr, NextAddr, Granularity) :- 275 pci_postorder(H, StartAddr, Next, Granularity), 276 pci_postorder_children(T, Next, NextAddr, Granularity). 277 278 279 280 281reserve_fixed_addresses([]). 282reserve_fixed_addresses([fixed(Class,SubClass,ProgIf)|T]) :- 283 findall(m(B,H), ( 284 device(_,Addr,_,_,Class, SubClass, ProgIf,_),bar(Addr,BAR,B,H,_,_,_) 285 ), 286 FixedList), 287 ( foreach(m(B,H),FixedList) 288 do 289 assert(fixed_memory(B,H)) 290 ), 291 reserve_fixed_addresses(T). 292 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 359 360%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 361% tools 362%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 363 364adjust_range(X, buselement(T,A,Sec,B1,H1,S,Tp,PF, PCIe, Bits), buselement(T,A,Sec,B2,H2,S,Tp,PF, PCIe, Bits)) :- 365 B2 is B1 + X, 366 H2 is H1 + X. 367 368back_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)) :- 369 B is BP * Granularity, 370 H is HP * Granularity, 371 S is SP * Granularity. 372 373base(buselement(_,_,_,Base,_,_,_,_,_,_),Base). 374high(buselement(_,_,_,_,High,_,_,_,_,_),High). 375size(buselement(_,_,_,_,_,Size,_,_,_,_),Size). 376 377 378compute_bridge_size([]). 379compute_bridge_size([buselement(device,_,_,_,_,_,_,_,_,_)|T]) :- 380 compute_bridge_size(T). 381compute_bridge_size([buselement(bridge,_,_,Base,High,Size,_,_,_,_)|T]) :- 382 Size is High - Base, 383 compute_bridge_size(T). 384 385 386%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 387% store the new values of the BARs 388%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 389replace_current_BAR_values(L) :- 390 delete_current_BAR_values(L), 391 store_current_BAR_values(L). 392 393store_current_BAR_values([]). 394store_current_BAR_values([H|T]) :- 395 ( buselement(device,Addr,BAR,Base,High,Size,_,_,_,_) = H -> 396 assert(currentbar(Addr,BAR,Base,High,Size)); 397 true 398 ), 399 store_current_BAR_values(T). 400 401 402delete_current_BAR_values([]). 403delete_current_BAR_values([H|T]) :- 404 ( buselement(device,Addr,BAR,_,_,_,_,_,_,_) = H -> 405 ( currentbar(Addr,BAR,_,_,_) -> 406 retract(currentbar(Addr,BAR,_,_,_)); 407 true 408 ); 409 true 410 ), 411 delete_current_BAR_values(T). 412 413 414 415