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:-lib(ic).
11:-lib(ic_global).
12:-use_module(library(ic_edge_finder)).
13:- ["decoding_net4_support"].
14
15:- set_flag(print_depth, 200).
16
17:-dynamic(currentbar/5).
18:-dynamic(addr/3).
19
20pci_id_node_id(addr(Bus, Dev, Fun, BarNum, Pref), [Bus, Dev, Fun, BarNum, "PCI ":Pref]).
21pcibus_node_id(["PCIBUS"]).
22
23merge_window([], [], _).
24merge_window(R, [], L) :-
25    L = [R].
26
27merge_window([], [H | T], L) :-
28    merge_window(H, T, L).
29
30merge_window(range(B, H), [range(B2, H2) | T2], L) :-
31    (H == B2 ->
32        merge_window(range(B, H2), T2, L)
33    ;
34        merge_window([], T2, L2),
35        (member(L2, range(B2, H2)) ->
36            L = [range(B, H) | L2]
37        ;
38            append([range(B,H)], [range(B2, H2) | L2], L)
39        )
40    ).
41
42merge_address_windows(Addr, Output) :-
43
44    findall(range(Base, High), (rootbridge_address_window(Addr, mem(B, H)),
45                               LT1 is B / 4096,
46                               ceiling(LT1, LT2),
47                               integer(LT2, Base),
48                               HT1 is H / 4096,
49                               ceiling(HT1, HT2),
50                               integer(HT2, High)
51                               ),
52            Memory),
53    merge_window([], Memory, Output).
54
55get_address_window(Addr, Min, Max) :-
56    findall(Low, rootbridge_address_window(Addr, mem(Low, _)), LowList),
57    findall(High, rootbridge_address_window(Addr, mem(_, High)), HighList),
58    (not(LowList == []) ->
59        ic:minlist(LowList, Min)
60    ;
61        Min = 0
62    ),
63    (not(HighList == []) ->
64        ic:maxlist(HighList, Max)
65    ;
66        Max = 0
67    ).
68
69%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
70% main goal to be called from outside
71%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
72
73bridge_programming(Plan, NrElements) :-
74   Granularity is 4096,
75   %Granularity is 16384,
76   %Granularity is 1048576,
77% find all the root bridges
78    findall(root(Addr,Child,mem(LP,HP), Ranges),
79            (  rootbridge(Addr,Child, _),
80               merge_address_windows(Addr, Ranges),
81               get_address_window(Addr, L, H),
82               LT1 is L / Granularity,
83               ceiling(LT1, LT2),
84               integer(LT2, LP),
85               HT1 is H / Granularity,
86               ceiling(HT1, HT2),
87               integer(HT2, HP)
88            ),Roots),
89
90% exclude fixed memory from being allocated to devices
91    ( is_predicate(fixed_memory/2) ->
92        findall(range(ResLowP,ResSizeP),
93          (
94            fixed_memory(ResLow,ResHigh), T1 is ResLow / Granularity, floor(T1,T2),
95            integer(T2,ResLowP),
96            T3 is (ResHigh - ResLow) / Granularity,
97            ceiling(T3,T4),
98            integer(T4,ResSizeP)
99          ), ExclRangesFixed);
100        ExclRangesFixed = []
101    ),
102
103% exclude fixed memory from being allocated to devices
104%    ( is_predicate(memory_region/5) ->
105%        findall(range(ResLowP,ResSizeP),
106%          (
107%            memory_region(ResLow, _, Size, _, _),
108%            T1 is ResLow / Granularity,
109%            floor(T1,T2),
110%            integer(T2,ResLowP),
111%            T3 is Size / Granularity,
112%            ceiling(T3,T4),
113%            integer(T4,ResSizeP)
114%          ), ExclRangesMemory);
115%        ExclRangesMemory = []
116%    ),
117
118% exclude IOAPIC regions from being allocated to devices
119    ( is_predicate(ioapic/3) ->
120      % according to the spec we need 64Bytes in the Intel case. Reserve a page
121      % anyway, since currently we cannot query the real requested size
122      TSz is (4096 / Granularity),
123      ceiling(TSz, TSz2),
124      integer(TSz2, IOAPIC_MinSize),
125      findall(range(Bs,IOAPIC_MinSize),
126               (
127                ioapic(_,B,_),
128                T1 is B / Granularity,
129                floor(T1, T2),
130                integer(T2, Bs)
131               ),IOAPICs)
132      ;
133      IOAPICs = []
134    ),
135
136
137%if IOAPIC appears as BAR, do not add this region to the "avoid" regions
138    findall(range(SubBase, SubSize),
139        (
140            member(IOAPICRegionMember, IOAPICs),
141            range(SubBase, SubSize) = IOAPICRegionMember,
142            bar(_,_,OrigBarBase,_,_,_,_),
143            T27 is OrigBarBase / Granularity,
144            floor(T27, T28),
145            integer(T28, SubBase)
146        ), RemoveRegionList),
147    subtract(IOAPICs,RemoveRegionList,IOAPICsRemoveRegionList),
148
149%all the regions to avoid
150    append(ExclRangesFixed, IOAPICsRemoveRegionList, ExclRanges),
151    %append(ExclRanges2, ExclRangesMemory, ExclRanges),
152% create an assignment for all PCI buses (all root bridges and their children)
153    ( foreach(Root,Roots),
154      foreach(P,Plan),
155      foreach(L,Lengths),
156      param(Granularity),
157      param(ExclRanges),
158      param(IOAPICs)
159      do
160        bridge_assignment(P,Root, Granularity, ExclRanges, IOAPICs),
161        length(P,L)
162    ),
163    sum(Lengths,NrElements).
164
165%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
166% small tools
167%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
168
169adjust_range(X, buselement(T,A,Sec,B1,H1,S,Tp,PF, PCIe, Bits), buselement(T,A,Sec,B2,H2,S,Tp,PF, PCIe, Bits)) :-
170    B2 is B1 + X,
171    H2 is H1 + X.
172
173back_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)) :-
174    B is BP * Granularity,
175    H is HP * Granularity,
176    S is SP * Granularity.
177
178
179should_shift_bridge(Addr, Sec, Root, Granularity, OrigP) :-
180     secondary(Bus) = Sec,
181     (bar(addr(Bus, _, _), _ , Orig, _ , _, prefetchable, _ ) ->
182          % Bridge has a bar that is above shifting limit
183          Limit is 10000000*Granularity,
184          Orig @> Limit,
185          OrigF is Orig/Granularity,
186          integer(OrigF, OrigP)
187     ;
188        % The root bridge needs also shifting
189        root(RootAddr,childbus(MinBus,MaxBus), _, _) = Root,
190        (Addr == RootAddr ->
191          % get max bar since they are all under this rootbridge
192          findall(Orig, (bar(addr(Bus2, _ , _), _, Orig, _ , _, prefetchable , _),
193                         Bus2 @=< MaxBus,
194                         Bus2 @>= MinBus),
195                 Origs),
196          (not(Origs == []) ->
197              ic:maxlist(Origs, Max),
198              % Sanity checks
199              Limit is 10000000*Granularity,
200              Max @> Limit,
201              OrigF is Max/Granularity,
202              integer(OrigF, OrigP)
203          )
204        ;
205            false
206        )
207     ).
208
209shift_into_window_64_bit(Granularity, Windows, Root, buselement(T,A,Sec,B1,H1,S,Tp,PF, PCIe, Bits),
210                         buselement(T,A,Sec,B2,H2,S,Tp,PF, PCIe, Bits)) :-
211
212	(T == device ->
213        %BAR
214	    bar(A,Sec, Orig, _, _, _, _),
215
216        O1 is Orig / Granularity,
217        ceiling(O1, O2),
218        integer(O2, OrigP),
219
220        (OrigP > 10000000, PF == prefetchable, Bits == 64 ->
221            (foreach(range(B, H), Windows),
222             param(B2),
223             param(H2),
224             param(B1),
225             param(H1),
226             param(OrigP)
227             do
228                (H @>= OrigP, B @=< OrigP ->
229                    B2 is B1 + B,
230                    H2 is H1 + B
231                ;
232                    true
233                )
234            )
235        ;
236            B2 is B1,
237            H2 is H1
238        )
239    ;
240        %Bridge
241        findall(OrigP, (should_shift_bridge(A, Sec, Root, Granularity, OrigP),
242                        PF == prefetchable)
243                ,Origs),
244        (Origs == [] ->
245            %no bar under bridge with size > 10'000'000
246            B2 = B1,
247            H2 = H1
248        ;
249            ic:maxlist(Origs, Max),
250            (foreach(range(B, H), Windows),
251             param(B2),
252             param(B1),
253             param(H1),
254             param(H2),
255             param(Max)
256             do
257                (H @>= Max, B @=< Max ->
258                    B2 is B1 + B,
259                    H2 is H1 + B
260                ;
261                    true
262                )
263            )
264        )
265    ).
266
267create_vf_busele_list(VFs, LMem, HMem, Granularity) :-
268	 findall(buselement(device,addr(Bus,Dev,Fun),BAR,Base,High,SizeP,Type,Prefetch, PCIe, Bits),
269	            ( vf(pfaddr(_, _, _), addr(Bus, Dev, Fun)),
270                  device(PCIe, addr(Bus,Dev,Fun),_,_,_,_,_,_),
271	              bar(addr(Bus,Dev,Fun),BAR, _,Size, Type, Prefetch, Bits),
272                  ST1 is Size / Granularity,
273                  ceiling(ST1, ST2),
274                  integer(ST2, SizeP),
275                  Base::[LMem..HMem],
276                  High::[LMem..HMem]
277	            ),VFs).
278
279%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
280% Tree allocation etc, once per prefetchable and non prefetchable
281%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
282assign_addresses(Plan, Root, Tree, Granularity, ExclRanges, IOAPICs, HMem2) :-
283    root(_ , _, mem(LMem,HMem), Ranges) = Root,
284    setrange(Tree,_,_,_),
285    nonoverlap(Tree),
286    naturally_aligned(Tree, 256, LMem, HMem, HMem2, _),
287    %naturally_aligned(Tree, 256, LMem, HMem, HMem2, ExtraVars),
288    tree2list(Tree,ListaU),
289    sort(6, >=, ListaU, Lista),
290    not_overlap_memory_ranges(Lista, ExclRanges),
291
292    keep_orig_addr(Lista, 12, 3, _, _, _, _),
293    keep_ioapic_bars(Lista, IOAPICs),
294    %labelall(Lista, ExtraVars),
295    labelall(Lista),
296
297    % Shift 64 bit addresses back into their window since
298    % disjunctive() only takes numbers uf to 10'000'000
299    maplist(shift_into_window_64_bit(Granularity, Ranges, Root),Lista, Plan).
300
301%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
302% Building the decoding net
303%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
304build_decoding_net(Tree, Granularity, RelativeAddr):-
305    t(buselement(_, addr(Bus, Dev, Fun), BarNum, Base, High, _, _, Pref, _, _) ,Children) = Tree,
306    Size is High - Base,
307    pci_id_node_id(addr(Bus, Dev, Fun, BarNum, Pref), Id),
308
309    (Children == [] ->
310        % This is a node that has to accept since there are no children
311        (Size @> 0 ->
312            SP is Size*Granularity -1,
313            (RelativeAddr == true ->
314                %writeln(bar_new(region(Id, block(0, SP)))),
315                assert_accept(region(Id, block(0, SP)))
316            ;
317                B is Base*Granularity,
318                H is High*Granularity -1,
319                %writeln(bar_new(region(Id, block(B, H)))),
320                assert_accept(region(Id, block(B, H)))
321            )
322        ;
323            true
324        )
325    ;
326        % This is a node that has to translate since there are children on this bridge
327        %writeln("=================================================="),
328        ( foreach(El, Children),
329          param(Id),
330          param(Base),
331          param(Granularity),
332          param(RelativeAddr)
333          do
334            t(buselement(_, addr(Bus2, Dev2, Fun2), BarNum2, Base2, High2, _, _, Pref2, _, _) , _) = El,
335            pci_id_node_id(addr(Bus2, Dev2, Fun2, BarNum2, Pref2), PCIId),
336
337            B2 is Base2 * Granularity,
338            H2 is High2 * Granularity -1,
339            S is (H2-B2),
340
341            (RelativeAddr == true ->
342                AcceptStart is (Base2 - Base) * Granularity,
343                AcceptEnd is AcceptStart + S,
344                ChildStart is AcceptStart
345            ;
346                AcceptStart is B2,
347                AcceptEnd is H2,
348                ChildStart is B2
349            ),
350
351            (S @> 0 ->
352                assert_translate(region(Id, block(AcceptStart, AcceptEnd)), name(PCIId, ChildStart)),
353                %writeln(bridge_new((region(Id, block(AcceptStart, AcceptEnd)), S, name(PCIId, ChildStart)))),
354                build_decoding_net(El, Granularity, RelativeAddr)
355            ;
356                true
357            )
358        )
359        %writeln("==================================================")
360    ).
361
362
363% TODO 32 Bit prefetchable
364%add_root_to_decoding_net(Addr, MinBus, Base, High, Ranges, Prefetchable) :-
365%    Size is High - Base,
366%    (Size @> 0 ->
367%        addr(Bus, Dev, Fun) = Addr,
368%        pci_id_node_id(addr(Bus, Dev, Fun, secondary(MinBus)), PCIId),
369%        pcibus_node_id(Id),
370%        ( Prefetchable == prefetchable ->
371%            (foreach(range(B, H), Ranges),
372%             param(Id),
373%             param(Base),
374%             param(High),
375%             param(PCIId)
376%             do
377%                ( Base @>= B, Base @=< H, High @>= H,
378%                    writeln("Prefetchable"),
379%                    writeln((region(Id, block(Base, H)), name(PCIId, Base))),
380%                    assert_translate(region(Id, block(Base, H)), name(PCIId, Base))
381%                ;
382%                    true
383%                ),
384%
385%                (  Base @=< B, Base @=< H, High @=< H,
386%                    writeln("Prefetchable"),
387%                    writeln((region(Id, block(B, High)), name(PCIId, B))),
388%                    assert_translate(region(Id, block(B, High)), name(PCIId, B))
389%                ;
390%                    true
391%                )
392%            )
393%        ;
394%            writeln("Nonprefetchable"),
395%            writeln((region(Id, block(Base, High)), name(PCIId, Base))),
396%            assert_translate(region(Id, block(Base, High)), name(PCIId, Base))
397%        )
398%    ).
399
400add_root_to_decoding_net(Addr, MinBus, Pref, Base, High) :-
401        addr(Bus, Dev, Fun) = Addr,
402        pci_id_node_id(addr(Bus, Dev, Fun, secondary(MinBus), Pref), PCIId),
403        pcibus_node_id(Id),
404        assert_translate(region(Id, block(Base, High)), name(PCIId, Base)).
405
406%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
407% the main part of the allocation. Called once per root bridge
408%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
409
410bridge_assignment(Plan, Root, Granularity, ExclRanges, IOAPICs) :-
411    root(Addr,childbus(MinBus,MaxBus),mem(LMem,HMem), Ranges) = Root,
412    X is HMem - LMem,
413    Tmp is 4294963200 / Granularity,
414    ceiling(Tmp, Tmp2),
415    integer(Tmp2, HMem2),
416    Type = mem,
417
418% prefetchable (Shifts addresses above 10'000'000 to 0)
419    constrain_bus(Granularity, Type, prefetchable, Addr,MinBus,MaxBus,LMem,HMem,BusElementListP, Ranges),
420    RBaseP::[LMem..HMem],
421    RHighP::[LMem..HMem],
422    RSizeP::[0..X],
423    devicetree(BusElementListP,buselement(bridge,Addr,secondary(MinBus),RBaseP,RHighP,RSizeP, Type, prefetchable, pcie, 0),TP),
424
425% nonprefetchable, Highest address must be less than 4GB
426    constrain_bus(Granularity, Type, nonprefetchable, Addr,MinBus,MaxBus,LMem,HMem2,BusElementListNP, Ranges),
427    RBaseNP::[LMem..HMem2],
428    RHighNP::[LMem..HMem2],
429    RSizeNP::[0..X],
430    devicetree(BusElementListNP,buselement(bridge,Addr,secondary(MinBus),RBaseNP,RHighNP,RSizeNP, Type, nonprefetchable, pcie, 0),TNP),
431
432    assign_addresses(PPlan, Root, TP, Granularity, ExclRanges, IOAPICs, HMem2),
433    assign_addresses(NPPlan, Root, TNP, Granularity, ExclRanges, IOAPICs, HMem2),
434
435    append(PPlan, NPPlan, Plan),
436    subtract(PPlan, [buselement(bridge,Addr, _, _, _,_,_,prefetchable,_,_)],PPlan2),
437    devicetree(PPlan2, buselement(bridge,Addr,secondary(MinBus), RBaseP, RHighP, RSizeP, Type, prefetchable, _, _), TP2),
438    add_root_to_decoding_net(Addr, MinBus, prefetchable, RBaseP, RHighP),
439    build_decoding_net(TP2, Granularity, true),
440
441    %Add TNP Root
442    subtract(NPPlan, [buselement(bridge,Addr, _, _, _,_,_,nonprefetchable,_,_)],NPPlan2),
443    devicetree(NPPlan2, buselement(bridge,Addr,secondary(MinBus),RBaseNP,RHighNP,RSizeNP, Type, prefetchable, _, _), TNP2),
444    add_root_to_decoding_net(Addr, MinBus, nonprefetchable, RBaseNP, RHighNP),
445    build_decoding_net(TNP2, Granularity, true).
446
447
448%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
449% instantiating the variables
450%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
451
452base(buselement(_,_,_,Base,_,_,_,_,_,_),Base).
453high(buselement(_,_,_,_,High,_,_,_,_,_),High).
454size(buselement(_,_,_,_,_,Size,_,_,_,_),Size).
455
456labelall(BusElementList) :-
457    maplist(base, BusElementList, Base),
458    maplist(size, BusElementList, Size),
459    maplist(high, BusElementList, High),
460    append(Size, Base , L1),
461    append(L1, High , L2),
462    labeling(L2).
463
464labelall(BusElementList, ExtraVars) :-
465    maplist(base, BusElementList, Base),
466    maplist(size, BusElementList, Size),
467    maplist(high, BusElementList, High),
468    append(Size, Base , L1),
469    append(L1, High , L2),
470    append(L2, ExtraVars , L3),
471    labeling(L3).
472
473%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
474% create the list of devices and bridges in form of buselements and create the
475% variables.
476% we care about the allocation of memory mapped registers here, therefore we only
477% look at bar located in "mem", not "io"
478%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
479
480constrain_bus(Granularity, Type, Prefetch, RootAddr,Bus,MaxBus,LMem,HMem,OutBusElementList, Ranges) :-
481    constrain_bus_ex(Granularity, Type, Prefetch, RootAddr,Bus,MaxBus,LMem,HMem,[],OutBusElementList, Ranges).
482
483constrain_bus_ex(_, _, _, _,Bus,MaxBus,_,_,InL,InL, _) :- Bus > MaxBus.
484constrain_bus_ex(Granularity, Type, Prefetch, RootAddr,Bus,MaxBus,LMem,HMem,InBusElementList,OutBusElementList, Ranges) :-
485    Bus =< MaxBus,
486    % 32 Bit device and bridges that are non prefetchable require an address below 4GB
487    Tmp is 4294963200 / Granularity,
488    ceiling(Tmp, Tmp2),
489    integer(Tmp2, HMem2),
490    ( is_predicate(bridge/8) ->
491	    findall(buselement(bridge,addr(Bus,Dev,Fun),secondary(Sec),Base,High,Size,Type,Prefetch, PCIe, 0),
492	            ( bridge(PCIe, addr(Bus,Dev,Fun), _, _, _, _, _, secondary(Sec)),
493	              not addr(Bus,Dev,Fun) = RootAddr,
494                  (Prefetch == nonprefetchable ->
495                    SMax is HMem2 - LMem,
496	                Base::[LMem..HMem2],
497	                High::[LMem..HMem2],
498                    Size::[0..SMax]
499                  ;
500                    SMax is HMem - LMem,
501	                Base::[LMem..HMem],
502	                High::[LMem..HMem],
503                    Size::[0..SMax]
504                  )
505	            ),BridgeList);
506        BridgeList = []
507    ),
508    ( is_predicate(device/8) ->
509	    findall(buselement(device,addr(Bus,Dev,Fun),BAR,Base,High,SizeP,Type,Prefetch, PCIe, Bits),
510	            ( device(PCIe, addr(Bus,Dev,Fun),_,_,_,_,_,_),
511	              bar(addr(Bus,Dev,Fun),BAR, Orig, Size, Type, Prefetch, Bits),
512                  ST1 is Size / Granularity,
513                  ceiling(ST1, ST2),
514                  integer(ST2, SizeP),
515
516                  O1 is Orig / Granularity,
517                  ceiling(O1, O2),
518                  integer(O2, OrigP),
519                  (Bits == 32 ->
520                    Base::[LMem..HMem2],
521                    High::[LMem..HMem2],
522                    % We have multiple ranges, add constraint for each of them.
523                    (foreach(range(B, H), Ranges),
524                     param(OrigP),
525                     param(Base),
526                     param(High)
527                     do
528                        (H @>= OrigP, B @=< OrigP ->
529                            Base::[B..H],
530                            High::[B..H]
531                        ;
532                            true
533                        )
534                    )
535                  ;
536                    Base::[LMem..HMem],
537                    High::[LMem..HMem],
538                    % We have multiple ranges, add constraint for each of them.
539                    (foreach(range(B, H), Ranges),
540                     param(OrigP),
541                     param(Base),
542                     param(High)
543                     do
544                        (H @>= OrigP, B @=< OrigP ->
545                            (OrigP > 10000000 ->
546                                %shift to smallest address
547                                H2 is H - B,
548                                Base::[0..H2],
549                                High::[0..H2]
550                            ;
551                                Base::[B..H],
552                                High::[B..H]
553                            )
554                        ;
555                            true
556                        )
557                    )
558                  )
559	            ),DeviceList);
560        DeviceList = []
561    ),
562    append(BridgeList, DeviceList, MyBusElementList),
563    append(InBusElementList, MyBusElementList, NewBusElementList),
564    NextBus is Bus + 1,
565    constrain_bus_ex(Granularity, Type, Prefetch, RootAddr, NextBus, MaxBus, LMem,HMem,NewBusElementList,OutBusElementList, Ranges).
566
567
568%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
569% create the PCI(e) device tree from a list of "buselement" and return it in Tree
570%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
571
572devicetree(List,CurrRoot,Tree) :-
573    buselement(bridge,_,secondary(Sec),_,_,_,_,_,_,_) = CurrRoot,
574    findall(X,(
575               member(Y,List),
576               buselement(_,addr(Sec,_,_),_,_,_,_,_,_,_,_) = Y,
577               devicetree(List, Y, X)),Children
578           ),
579    Tree = t(CurrRoot,Children).
580
581devicetree(_,CurrRoot,Tree) :-
582    buselement(device,_,_,_,_,_,_,_,_,_) = CurrRoot,
583    Tree = t(CurrRoot, []).
584
585
586%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
587% convert a tree to a list of buselements
588%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
589
590tree2list([],[]).
591tree2list(Tree, List) :-
592    t(Node,Children) = Tree,
593    ( foreach(El,Children),
594      foreach(L1,ChildList)
595      do
596        tree2list(El,L1)
597    ),
598    flatten(ChildList,L2),
599    List = [Node|L2].
600
601
602
603%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
604% store the new values of the BARs
605%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
606replace_current_BAR_values(L) :-
607    delete_current_BAR_values(L),
608    store_current_BAR_values(L).
609
610store_current_BAR_values([]).
611store_current_BAR_values([H|T]) :-
612    ( buselement(device,Addr,BAR,Base,High,Size,_,_,_,_) = H ->
613         assert(currentbar(Addr,BAR,Base,High,Size));
614        true
615    ),
616    store_current_BAR_values(T).
617
618
619delete_current_BAR_values([]).
620delete_current_BAR_values([H|T]) :-
621    ( buselement(device,Addr,BAR,_,_,_,_,_,_,_) = H ->
622        ( currentbar(Addr,BAR,_,_,_) ->
623            retract(currentbar(Addr,BAR,_,_,_));
624            true
625        );
626        true
627    ),
628    delete_current_BAR_values(T).
629
630
631
632
633%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
634% add constraints to the tree
635%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
636
637range(buselement(_,_,_,Base,High,_,_,_,_,_),range(Base, High)).
638
639% make sure that the bridge has a range which includes all the children
640setrange(Tree,SubTreeSize,SubTreeMin,SubTreeMax) :-
641    t(Node,Children) = Tree,
642    ( foreach(El,Children),
643      foreach(Sz,SizeList),
644      foreach(Mi,MinList),
645      foreach(Ma,MaxList)
646      do
647        setrange(El,Sz,Mi,Ma)
648    ),
649    ic_global:sumlist(SizeList,Size),
650    buselement(_,_,_,Base,High,ElemSize,_,_,_,_) = Node,
651    ElemSize #>= Size,
652    ( not MinList=[] ->
653        ic:minlist(MinList,Min),
654        ic:maxlist(MaxList,Max),
655        Min #>= Base,
656        Max #=< High;
657        true
658    ),
659    High #= Base + ElemSize,
660    SubTreeSize #= ElemSize,
661    SubTreeMin #= Base,
662    SubTreeMax #= High.
663setrange([],0,_,_).
664
665
666% make sure that the children do not overlap
667child(t(C,_),C).
668nonoverlap(Tree) :-
669    t(_ ,Children) = Tree,
670    maplist(child,Children,ChildList),
671    ( not ChildList=[] ->
672        maplist(base,ChildList,Base),
673        maplist(size,ChildList,Size),
674        disjunctive(Base, Size)
675        ;
676        true
677    ),
678    ( foreach(El, Children)
679      do
680        nonoverlap(El)
681    ).
682
683
684naturally_aligned(Tree, BridgeAlignment, LMem, HMem, HMem2, ExtraVars) :-
685
686    t(Node,Children) = Tree,
687    ( buselement(device,_,_,Base,High,Size,_,_,_,Bits) = Node ->
688      Divisor is Size,
689      (Bits == 32 ->
690        LimitRange is 1
691      ;
692        LimitRange is 0
693      )
694    ;
695      buselement(bridge, Addr,_,Base,High,_, _, Prefetch,_,_) = Node ->
696      Divisor is BridgeAlignment,
697      (not Addr == addr(-1,-1,-1) ->
698          (Prefetch == nonprefetchable ->
699            LimitRange is 1
700          ;
701            LimitRange is 0
702          )
703      ;
704        LimitRange is 0
705      )
706    ),
707
708    ( LimitRange == 1 ->
709        T1 is (HMem2 - LMem) / Divisor
710    ;
711        T1 is (HMem - LMem) / Divisor
712    ),
713
714    ceiling(T1, T2),
715    integer(T2, Nr),
716    N::[0..Nr],
717    N2::[0..Nr],
718    mod(LMem,Divisor,Remainder),
719    ( Remainder =:= 0 ->
720        Corr is 0;
721        Corr is Divisor - Remainder
722    ),
723    Base #= N*Divisor + LMem + Corr,
724    High #>= Base,
725    High #= N2*Divisor + LMem + Corr,
726    ( foreach(El, Children),
727      fromto([N], XtraIn, XtraOut, ExtraVars),
728      param(BridgeAlignment),
729      param(LMem),
730      param(HMem),
731      param(HMem2)
732      do
733        naturally_aligned(El, BridgeAlignment, LMem, HMem, HMem2, E1),
734        append(XtraIn, E1, XtraOut)
735    ).
736
737
738% do not overlap with the given list of memory ranges
739not_overlap_memory_ranges([], _).
740not_overlap_memory_ranges(_, []).
741not_overlap_memory_ranges([buselement(bridge,_,_,_,_,_,_,_,_,_)|PCIList], MemoryRanges) :-
742    not_overlap_memory_ranges(PCIList, MemoryRanges).
743not_overlap_memory_ranges([H|PCIList], MemoryRanges) :-
744    ( foreach(range(RBase,RSize),MemoryRanges),
745      param(H)
746      do
747      buselement(device,_,_,Base,_,Size,_,_,_,_) = H,
748      append([Base],[RBase],Bases),
749      append([Size],[RSize],Sizes),
750      disjunctive(Bases,Sizes)
751    ),
752    not_overlap_memory_ranges(PCIList, MemoryRanges).
753
754
755keep_orig_addr([], _, _, _, _, _, _).
756keep_orig_addr([H|Buselements], Class, SubClass, ProgIf, Bus, Dev, Fun) :-
757    ( buselement(device,addr(Bus,Dev,Fun),BAR,Base,_,_,_,_,_,_) = H,
758      device(_,addr(Bus,Dev,Fun),_,_,Class, SubClass, ProgIf,_),
759      bar(addr(Bus,Dev,Fun),BAR,OrigBase,_,_,_,_) ->
760       T1 is OrigBase / 4096,
761       floor(T1,T2),
762       integer(T2,KeepBase),
763        Base #= KeepBase
764        ;
765        true
766    ),
767    keep_orig_addr(Buselements, Class, SubClass, ProgIf, Bus, Dev, Fun).
768
769% on some machines (sbrinz1) one of the two IOAPICs appears as a BAR
770% on a device which claims to be a RAM memory controller. If this occurs,
771% we want to avoid moving this BAR as otherwise the IOAPIC cannot be reached
772% anymore.
773keep_ioapic_bars(_, []).
774keep_ioapic_bars(Buselements, [H|IOAPICList]) :-
775    (
776    range(B, _) = H,
777    bar(addr(Bus,Dev,Fun),_,OrigBase,_,_,_,_),
778    T1 is OrigBase / 4096,
779    floor(T1,T2),
780    integer(T2,KeepBase),
781    KeepBase =:= B ->
782    keep_orig_addr(Buselements, _, _, _, Bus, Dev, Fun);
783    true
784    ),
785    keep_ioapic_bars(Buselements, IOAPICList).
786
787
788:-dynamic(root/4).
789:-dynamic(mem/2).
790:-dynamic(childbus/2).
791
792setup_test(Tree) :-
793    ["clean_facts/babybel1.pl"],
794    Granularity is 4096,
795    Addr = addr(0, 0, 0),
796    rootbridge(Addr, childbus(MinBus, MaxBus), _),
797    merge_address_windows(Addr, Ranges),
798    get_address_window(Addr, L, H),
799    LT1 is L / Granularity,
800    ceiling(LT1, LT2),
801    integer(LT2, LP),
802    HT1 is H / Granularity,
803    ceiling(HT1, HT2),
804    integer(HT2, HP),
805
806    Tmp is 4294963200 / Granularity,
807    ceiling(Tmp, Tmp2),
808    integer(Tmp2, HMem2),
809
810    Root = root(Addr, childbus(MinBus, MaxBus), mem(LP, HP), Ranges),
811
812    % prefetchable (Shifts addresses above 10'000'000 to 0)
813    constrain_bus(Granularity, mem, prefetchable, Addr,MinBus,MaxBus,LP,HP,BusElementListP, Ranges),
814    RBaseP::[LP..HP],
815    RHighP::[LP..HP],
816    Size is HP - LP,
817    RSizeP::[0..Size],
818    devicetree(BusElementListP,buselement(bridge,Addr,secondary(MinBus),RBaseP,RHighP,RSizeP,mem, prefetchable, _, _),Tree),
819    assign_addresses(_, Root, Tree, Granularity, [], [], HMem2).
820
821test_tree_shift :-
822    setup_test(Tree),
823    tree2list(Tree, Lista),
824    writeln(Lista),
825    devicetree(Lista, Tree2),
826    writeln(Tree2).
827
828
829
830
831