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:-lib(ic).
11:-lib(ic_global).
12:-use_module(library(ic_edge_finder)).
13
14:- set_flag(print_depth, 200).
15
16:-dynamic(currentbar/5).
17
18% :-include("../data/data_hand.txt").
19% :-include("../data/data_qemu_hand.txt").
20% :-include("../data/data_qemu.txt").
21% :-include("../data/data_nos3.txt").
22% :-include("../data/data_nos4.txt").
23% :-include("../data/data_nos5.txt").
24% :-include("../data/data_nos6.txt").
25% :-include("../data/data_gruyere.txt").
26% :-include("../data/data_sbrinz1.txt").
27% :-include("../data/data_loner.txt").
28
29
30
31%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
32% main goal to be called from outside
33%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
34
35bridge_programming(Plan, NrElements) :-
36    Granularity is 4096,
37% find all the root bridges
38    findall(root(Addr,Child,mem(LP,HP)),
39            (  rootbridge(Addr,Child,mem(L,H)),
40               LT1 is L / Granularity,
41               ceiling(LT1, LT2),
42               integer(LT2, LP),
43               HT1 is H / Granularity,
44               ceiling(HT1, HT2),
45               integer(HT2, HP)
46            ),Roots),
47% exclude fixed memory from being allocated to devices
48    ( is_predicate(fixed_memory/2) ->
49        findall(range(ResLowP,ResSizeP),
50          (
51            fixed_memory(ResLow,ResHigh), T1 is ResLow / Granularity, floor(T1,T2),
52            integer(T2,ResLowP),
53            T3 is (ResHigh - ResLow) / Granularity,
54            ceiling(T3,T4),
55            integer(T4,ResSizeP)
56          ), ExclRangesFixed);
57        ExclRangesFixed = []
58    ),
59% exclude IOAPIC regions from being allocated to devices
60    ( is_predicate(ioapic/3) ->
61      % according to the spec we need 64Bytes in the Intel case. Reserve a page
62      % anyway, since currently we cannot query the real requested size
63      TSz is (4096 / Granularity),
64      ceiling(TSz, TSz2),
65      integer(TSz2, IOAPIC_MinSize),
66      findall(range(Bs,IOAPIC_MinSize),
67               (
68                ioapic(_,B,_),
69                T1 is B / Granularity,
70                floor(T1, T2),
71                integer(T2, Bs)
72               ),IOAPICs)
73      ;
74      IOAPICs = []
75    ),
76
77%if IOAPIC appears as BAR, do not add this region to the "avoid" regions
78    findall(range(SubBase, SubSize),
79        (
80            member(IOAPICRegionMember, IOAPICs),
81            range(SubBase, SubSize) = IOAPICRegionMember,
82            bar(_,_,OrigBarBase,_,_,_,_),
83            T27 is OrigBarBase / Granularity,
84            floor(T27, T28),
85            integer(T28, SubBase)
86        ), RemoveRegionList),
87    subtract(IOAPICs,RemoveRegionList,IOAPICsRemoveRegionList),
88
89%all the regions to avoid
90    append(ExclRangesFixed, IOAPICsRemoveRegionList, ExclRanges),
91
92% create an assignment for all PCI buses (all root bridges and their children)
93    ( foreach(Root,Roots),
94      foreach(P,Plan),
95      foreach(L,Lengths),
96      param(Granularity),
97      param(ExclRanges),
98      param(IOAPICs)
99      do
100        bridge_assignment(P,Root, Granularity, ExclRanges, IOAPICs),
101        length(P,L)
102    ),
103    sum(Lengths,NrElements).
104
105
106%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
107% small tools
108%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
109
110adjust_range(X, buselement(T,A,Sec,B1,H1,S,Tp,PF, PCIe, Bits), buselement(T,A,Sec,B2,H2,S,Tp,PF, PCIe, Bits)) :-
111    B2 is B1 + X,
112    H2 is H1 + X.
113
114back_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)) :-
115    B is BP * Granularity,
116    H is HP * Granularity,
117    S is SP * Granularity.
118
119
120%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
121% the main part of the allocation. Called once per root bridge
122%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
123
124bridge_assignment(Plan, Root, Granularity, ExclRanges, IOAPICs) :-
125    root(Addr,childbus(MinBus,MaxBus),mem(LMem,HMem)) = Root,
126    X is HMem - LMem,
127    Type = mem,
128
129% prefetchable
130    constrain_bus(Granularity, Type, prefetchable, Addr,MinBus,MaxBus,LMem,HMem,BusElementListP),
131    RBaseP::[LMem..HMem],
132    RHighP::[LMem..HMem],
133    RSizeP::[0..X],
134    devicetree(BusElementListP,buselement(bridge,Addr,secondary(MinBus),RBaseP,RHighP,RSizeP, Type, prefetchable, _, _),TP),
135
136% nonprefetchable
137    constrain_bus(Granularity, Type, nonprefetchable, Addr,MinBus,MaxBus,LMem,HMem,BusElementListNP),
138    RBaseNP::[LMem..HMem],
139    RHighNP::[LMem..HMem],
140    RSizeNP::[0..X],
141    devicetree(BusElementListNP,buselement(bridge,Addr,secondary(MinBus),RBaseNP,RHighNP,RSizeNP, Type, nonprefetchable, _, _),TNP),
142
143% pseudo-root of both trees
144    PseudoBase::[LMem..HMem],
145    PseudoHigh::[LMem..HMem],
146    PseudoSize::[0..X],
147    T = t(buselement(bridge, addr(-1, -1, -1), childbus(-1, -1), PseudoBase, PseudoHigh, PseudoSize, _, _, _, _), [TP, TNP]),
148    setrange(T,_,_,_),
149    nonoverlap(T),
150    naturally_aligned(T, 256, LMem, HMem),
151    tree2list(T,ListaU),
152    sort(6, >=, ListaU, Lista),
153    not_overlap_memory_ranges(Lista, ExclRanges),
154    keep_orig_addr(Lista, 12, 3, _, _, _, _),
155    keep_ioapic_bars(Lista, IOAPICs),
156    labelall(Lista),
157    subtract(Lista,[buselement(bridge,Addr,_,_,_,_,_,prefetchable,_,_)],Pl3),
158    subtract(Pl3,[buselement(bridge,Addr,_,_,_,_,_,nonprefetchable,_,_)],Pl2),
159    subtract(Pl2,[buselement(bridge,addr(-1,-1,-1),_,_,_,_,_,_,_,_)],Pl),
160    maplist(adjust_range(0),Pl,PR),
161    maplist(back_to_bytes(Granularity),PR,Plan).
162
163% dot output:
164%    PrBaseBytePref is RBaseP * Granularity,
165%    PrHighBytePref is RHighP * Granularity,
166%    PrBaseByteNonPref is RBaseNP * Granularity,
167%    PrHighByteNonPref is RHighNP * Granularity,
168%    plan_to_dot(Granularity, Plan, Root, PrBaseBytePref, PrHighBytePref, PrBaseByteNonPref, PrHighByteNonPref).
169
170
171%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
172% instantiating the variables
173%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
174
175base(buselement(_,_,_,Base,_,_,_,_,_,_),Base).
176high(buselement(_,_,_,_,High,_,_,_,_,_),High).
177size(buselement(_,_,_,_,_,Size,_,_,_,_),Size).
178
179labelall(BusElementList) :-
180    maplist(base, BusElementList, Base),
181    maplist(high, BusElementList, High),
182    maplist(size, BusElementList, Size),
183    append(Base, High, L1),
184    append(L1, Size, L2),
185    labeling(L2).
186
187
188
189%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
190% create the list of devices and bridges in form of buselements and create the
191% variables.
192% we care about the allocation of memory mapped registers here, therefore we only
193% look at bar located in "mem", not "io"
194%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
195
196constrain_bus(Granularity, Type, Prefetch, RootAddr,Bus,MaxBus,LMem,HMem,OutBusElementList) :-
197    constrain_bus_ex(Granularity, Type, Prefetch, RootAddr,Bus,MaxBus,LMem,HMem,[],OutBusElementList).
198
199constrain_bus_ex(_, _, _, _,Bus,MaxBus,_,_,InL,InL) :- Bus > MaxBus.
200constrain_bus_ex(Granularity, Type, Prefetch, RootAddr,Bus,MaxBus,LMem,HMem,InBusElementList,OutBusElementList) :-
201    Bus =< MaxBus,
202    SMax is HMem - LMem,
203    ( is_predicate(bridge/8) ->
204	    findall(buselement(bridge,addr(Bus,Dev,Fun),secondary(Sec),Base,High,Size,Type,Prefetch, PCIe, 0),
205	            ( bridge(PCIe, addr(Bus,Dev,Fun), _, _, _, _, _, secondary(Sec)),
206	              not addr(Bus,Dev,Fun) = RootAddr,
207	              Base::[LMem..HMem],High::[LMem..HMem],Size::[0..SMax]
208	            ),BridgeList);
209        BridgeList = []
210    ),
211    ( is_predicate(device/8) ->
212	    findall(buselement(device,addr(Bus,Dev,Fun),BAR,Base,High,SizeP,Type,Prefetch, PCIe, Bits),
213	            ( device(PCIe, addr(Bus,Dev,Fun),_,_,_,_,_,_),
214	              bar(addr(Bus,Dev,Fun),BAR,_,Size, Type, Prefetch, Bits),
215	              Base::[LMem..HMem],High::[LMem..HMem],
216	              ST1 is Size / Granularity,
217	              ceiling(ST1, ST2),
218	              integer(ST2, SizeP)
219	            ),DeviceList);
220        DeviceList = []
221    ),
222    append(BridgeList, DeviceList, MyBusElementList),
223    append(InBusElementList, MyBusElementList, NewBusElementList),
224    NextBus is Bus + 1,
225    constrain_bus_ex(Granularity, Type, Prefetch, RootAddr, NextBus, MaxBus, LMem,HMem,NewBusElementList,OutBusElementList).
226
227
228%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
229% create the PCI(e) device tree from a list of "buselement" and return it in Tree
230%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
231
232devicetree(List,CurrRoot,Tree) :-
233    buselement(bridge,_,secondary(Sec),_,_,_,_,_,_,_) = CurrRoot,
234    findall(X,(
235               member(Y,List),
236               buselement(_,addr(Sec,_,_),_,_,_,_,_,_,_,_) = Y,
237               devicetree(List, Y, X)),Children
238           ),
239    Tree = t(CurrRoot,Children).
240devicetree(_,CurrRoot,Tree) :-
241    buselement(device,_,_,_,_,_,_,_,_,_) = CurrRoot,
242    Tree = t(CurrRoot, []).
243
244
245%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
246% convert a tree to a list of buselements
247%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
248
249tree2list([],[]).
250tree2list(Tree, List) :-
251    t(Node,Children) = Tree,
252    ( foreach(El,Children),
253      foreach(L1,ChildList)
254      do
255        tree2list(El,L1)
256    ),
257    flatten(ChildList,L2),
258    List = [Node|L2].
259
260
261
262%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
263% store the new values of the BARs
264%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
265replace_current_BAR_values(L) :-
266    delete_current_BAR_values(L),
267    store_current_BAR_values(L).
268
269store_current_BAR_values([]).
270store_current_BAR_values([H|T]) :-
271    ( buselement(device,Addr,BAR,Base,High,Size,_,_,_,_) = H ->
272         assert(currentbar(Addr,BAR,Base,High,Size));
273        true
274    ),
275    store_current_BAR_values(T).
276
277
278delete_current_BAR_values([]).
279delete_current_BAR_values([H|T]) :-
280    ( buselement(device,Addr,BAR,_,_,_,_,_,_,_) = H ->
281        ( currentbar(Addr,BAR,_,_,_) ->
282            retract(currentbar(Addr,BAR,_,_,_));
283            true
284        );
285        true
286    ),
287    delete_current_BAR_values(T).
288
289
290
291
292%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
293% add constraints to the tree
294%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
295
296% make sure that the bridge has a range which includes all the children
297setrange(Tree,SubTreeSize,SubTreeMin,SubTreeMax) :-
298    t(Node,Children) = Tree,
299    ( foreach(El,Children),
300      foreach(Sz,SizeList),
301      foreach(Mi,MinList),
302      foreach(Ma,MaxList)
303      do
304        setrange(El,Sz,Mi,Ma)
305    ),
306    ic_global:sumlist(SizeList,Size),
307    buselement(_,_,_,Base,High,ElemSize,_,_,_,_) = Node,
308    ElemSize $>= Size,
309    ( not MinList=[] ->
310        ic:minlist(MinList,Min),
311        ic:maxlist(MaxList,Max),
312        Min $>= Base,
313        Max $=< High;
314        true
315    ),
316    High $= Base + ElemSize,
317    SubTreeSize $= ElemSize,
318    SubTreeMin $= Base,
319    SubTreeMax $= High.
320setrange([],0,_,_).
321
322
323% make sure that the children do not overlap
324child(t(C,_),C).
325nonoverlap(Tree) :-
326    t(_ ,Children) = Tree,
327    maplist(child,Children,ChildList),
328    ( not ChildList=[] ->
329        maplist(base,ChildList,Base),
330        maplist(size,ChildList,Size),
331        disjunctive(Base,Size);
332        true
333    ),
334    ( foreach(El, Children)
335      do
336        nonoverlap(El)
337    ).
338
339
340naturally_aligned(Tree, BridgeAlignment, LMem, HMem) :-
341    t(Node,Children) = Tree,
342    ( buselement(device,_,_,Base,High,Size,_,_,_,_) = Node ->
343      Divisor is Size
344      ;
345      buselement(bridge,_,_,Base,High,_,_,_,_,_) = Node ->
346      Divisor is BridgeAlignment
347    ),
348
349    T1 is (HMem - LMem) / Divisor,
350    ceiling(T1, T2),
351    integer(T2, Nr),
352    N::[0..Nr],
353    N2::[0..Nr],
354    mod(LMem,Divisor,Remainder),
355    ( Remainder =:= 0 ->
356        Corr is 0;
357        Corr is Divisor - Remainder
358    ),
359    Base $= N*Divisor + LMem + Corr,
360    High $>= Base,
361    High $= N2*Divisor + LMem + Corr,
362    ( foreach(El, Children),
363      param(BridgeAlignment),
364      param(LMem),
365      param(HMem)
366      do
367        naturally_aligned(El, BridgeAlignment, LMem, HMem)
368    ).
369
370
371% do not overlap with the given list of memory ranges
372not_overlap_memory_ranges([], _).
373not_overlap_memory_ranges(_, []).
374not_overlap_memory_ranges([buselement(bridge,_,_,_,_,_,_,_,_,_)|PCIList], MemoryRanges) :-
375    not_overlap_memory_ranges(PCIList, MemoryRanges).
376not_overlap_memory_ranges([H|PCIList], MemoryRanges) :-
377    ( foreach(range(RBase,RSize),MemoryRanges),
378      param(H)
379      do
380      buselement(device,_,_,Base,_,Size,_,_,_,_) = H,
381      append([Base],[RBase],Bases),
382      append([Size],[RSize],Sizes),
383      disjunctive(Bases,Sizes)
384    ),
385    not_overlap_memory_ranges(PCIList, MemoryRanges).
386
387
388keep_orig_addr([], _, _, _, _, _, _).
389keep_orig_addr([H|Buselements], Class, SubClass, ProgIf, Bus, Dev, Fun) :-
390    ( buselement(device,addr(Bus,Dev,Fun),BAR,Base,_,_,_,_,_,_) = H,device(_,addr(Bus,Dev,Fun),_,_,Class, SubClass, ProgIf,_),bar(addr(Bus,Dev,Fun),BAR,OrigBase,_,_,_,_) ->
391       T1 is OrigBase / 4096,
392       floor(T1,T2),
393       integer(T2,KeepBase),
394        Base $= KeepBase;
395        true
396    ),
397    keep_orig_addr(Buselements, Class, SubClass, ProgIf, Bus, Dev, Fun).
398
399% on some machines (sbrinz1) one of the two IOAPICs appears as a BAR
400% on a device which claims to be a RAM memory controller. If this occurs,
401% we want to avoid moving this BAR as otherwise the IOAPIC cannot be reached
402% anymore.
403keep_ioapic_bars(_, []).
404keep_ioapic_bars(Buselements, [H|IOAPICList]) :-
405    (
406    range(B, _) = H,
407    bar(addr(Bus,Dev,Fun),_,OrigBase,_,_,_,_),
408    T1 is OrigBase / 4096,
409    floor(T1,T2),
410    integer(T2,KeepBase),
411    KeepBase =:= B ->
412    keep_orig_addr(Buselements, _, _, _, Bus, Dev, Fun);
413    true
414    ),
415    keep_ioapic_bars(Buselements, IOAPICList).
416