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