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