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