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