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