1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 2% Copyright (c) 2018, 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, Universitaetsstrasse 6, CH-8092 Zurich. 8% Attn: Systems Group. 9%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 10 11%% This is the one-dimensional implementation of the decoding net. 12%% decoding_net3_multid contains the arbitrary dimensional implementation. 13 14% Some Conventions: 15% NodeId = identifier list 16% IAddr = [1,2,3] 17% Addr = [kind, 1] 18% IBlock block{..} 19% Block = [kind, block{..}] 20 21:- module(decoding_net3). 22 23:- use_module(allocator3). 24:- use_module(decoding_net3_state). 25 26 27%%% Bottom layer is storing the following facts in the State 28% accept(Region) 29% mapping(SrcRegion, DstName) 30% overlay(SrcNodeId, OutNodeId) 31% block_meta(NodeId, Bits, OutNodeId) -- Metadata for block reconfigurable nodes 32% block_conf(NodeId, VPN, PPN) -- For block reconfigurable nodes 33% in_use(NodeId, Block) -- Subset of accepted ranges that has been allocated 34 35state_valid([]). 36state_valid([accept(_) | As]) :- state_valid(As). 37state_valid([mapping(_,_) | As]) :- state_valid(As). 38state_valid([overlay(_,_) | As]) :- state_valid(As). 39state_valid([block_meta(_,_,_) | As]) :- state_valid(As). 40state_valid([block_conf(_,_,_) | As]) :- state_valid(As). 41state_valid([in_use(_,_) | As]) :- state_valid(As). 42 43:- export struct(block(base,limit)). 44:- export struct(region(node_id,blocks)). 45:- export struct(name(node_id,address)). 46 47:- lib(ic). 48 49%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 50%%%% Utilities for building the model layer 51%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 52 53inf_value(9223372036854775808). 54 55% TODO: Works only for one dimension. 56% ScanPoints is a list of points where the scanline (scanhyperplane?) should stop. 57scan_points(S, NodeId, ScanPoints) :- 58 Reg = region{node_id: NodeId}, 59 findall(Reg, state_query(S, mapping(Reg, _)), RegLi), 60 (foreach(Reg, RegLi), fromto([0], In, Out, Ptz) do 61 Reg = region{blocks: [_, block{base: B, limit: L}]}, 62 LP is L + 1, 63 append(In, [B,LP], Out) 64 ), 65 inf_value(Inf), 66 append(Ptz,[Inf], ScanPoints). 67 68% Max is bigger than Min and Max is smaller than all the bigger mapping bases 69max_not_translated_pt(S, NodeId, Min, Max) :- 70 Reg = region{node_id: NodeId}, 71 % Make sure Min is not in any Mapping. 72 not(state_query(S, mapping(region{node_id:NodeId,blocks:[_,block{base:Min}]}, _))), 73 inf_value(Inf), 74 findall(Reg, state_query(S, mapping(Reg, _)), RegLi), 75 (foreach(Reg, RegLi), param(Min), fromto(Inf, MaxIn, MaxOut, MaxMatch) do 76 Reg = region{blocks: [_, block{base: B}]}, 77 ( 78 ( B =< Min, MaxOut=MaxIn ) ; 79 ( min(MaxIn, B, MaxOut) ) 80 ) 81 ), 82 Max is MaxMatch - 1, 83 Max > Min. 84 85 86:- export test_scan_points/0. 87test_scan_points :- 88 S = [ 89 mapping( 90 region{node_id: ["IN"], blocks: [memory, block{base:100, limit:200}]}, 91 name{node_id: ["OUT"], address: [memory, 1]}), 92 mapping( 93 region{node_id: ["Dummy"], blocks: [memory, block{base:7, limit:77}]}, 94 name{node_id: ["OUT"], address: [memory, 1]}) 95 ], 96 scan_points(S, ["IN"], Points), 97 member(0, Points), 98 member(100, Points), 99 member(201, Points), 100 not(member(7, Points)), 101 not(member(77, Points)). 102 103:- export test_max_not_translated_pt/0. 104test_max_not_translated_pt :- 105 S = [ 106 mapping( 107 region{node_id: ["IN"], blocks: [memory, block{base:100, limit:200}]}, 108 name{node_id: ["OUT"], address: [memory, 1]}), 109 mapping( 110 region{node_id: ["Dummy"], blocks: [memory, block{base:7, limit:77}]}, 111 name{node_id: ["OUT"], address: [memory, 1]}) 112 ], 113 scan_points(S, ["IN"], Points), 114 max_not_translated_pt(S, ["IN"], 0, 99), 115 not(max_not_translated_pt(S, ["IN"], 100, _)). 116 117 118 119%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 120%%%% Model layer 121%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 122 123translate(S, SrcRegion, DstBase) :- 124 state_query(S, mapping(SrcRegion, DstBase)). 125 126% Transform the overlays into translate, but only where they don't match 127% an existing translate. 128translate(S, SrcRegion, DstBase) :- 129 SrcRegion = region{node_id:SrcNodeId}, 130 state_query(S, overlay(SrcNodeId, OverlayDest)), 131 scan_points(S, SrcNodeId, ScanPoints), 132 member(Base, ScanPoints), 133 max_not_translated_pt(S, SrcNodeId, Base, Limit), 134 SrcRegion = region{blocks:[memory, block{base: Base, limit: Limit}]}, 135 DstBase = name{node_id:OverlayDest, address: [memory, Base]}. 136 137:- export test_translate/0. 138test_translate :- 139 %Setup 140 S = [ 141 mapping( 142 region{node_id:["In"], blocks:[memory, block{base:1000,limit:2000}]}, 143 name{node_id: ["Out1"], address: [memory, 0]}), 144 overlay(["In"], ["Out2"]) 145 ], 146 Src = region{node_id:["In"]}, 147 %findall((Src,Dest), translate(S, Src, Dest), Li), 148 %(foreach((Src,Dest), Li) do 149 % printf("Src=%p, Dest=%p\n", [Src,Dest]) 150 %), 151 translate(S, 152 region{node_id:["In"], blocks:[memory, block{base:1000,limit:2000}]}, 153 name{node_id: ["Out1"], address: [memory, 0]}), 154 translate(S, 155 region{node_id:["In"], blocks:[memory, block{base:0,limit:999}]}, 156 name{node_id: ["Out2"], address: [memory, 0]}), 157 inf_value(Inf), Inf1 is Inf - 1, 158 translate(S, 159 region{node_id:["In"], blocks:[memory, block{base:2001,limit:Inf1}]}, 160 name{node_id: ["Out2"], address: [memory, 2001]}). 161 162 163 164%%%%% This is the old stricter "does not translate" predicate 165%%%does_not_translate(NodeId, [AKind,IAddr]) :- 166%%% %TODO take node_translate_block into account 167%%% findall(B, node_translate_dyn(NodeId, B, _, _), Blocks), 168%%% (foreach([AKind, IBlock], Blocks),param(IAddr),param(AKind) do 169%%% iblocks_nomatch(IAddr, IBlock) 170%%% ). 171%%% 172%%%test_does_not_translate :- 173%%% assert(node_translate_dyn( 174%%% ["In"], [memory, [block{base:1000,limit:2000}]], 175%%% ["Out1"], [memory, [block{base:0,limit:1000}]])), 176%%% does_not_translate(["In"], [memory, [500]]). 177 178%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 179%%%% Utilities 180%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 181 182:-export iaddress_aligned/2. 183iaddress_aligned(A, Bits) :- 184 BlockSize is 2^Bits, 185 BlockNum #>= 0, 186 A #= BlockNum * BlockSize. 187 188address_aligned([_, IAddress], Bits) :- 189 iaddress_aligned(IAddress, Bits). 190 191name_aligned(Name, Bits) :- 192 name{address: Addr} = Name, 193 address_aligned(Addr, Bits). 194 195:- export test_alignment/0. 196test_alignment :- 197 536870912 #< IAddr, 198 iaddress_aligned(IAddr, 21), 199 labeling([IAddr]), 200 IAddr = 538968064. 201 202iblock_match(A, block{base: B, limit: L}) :- 203 B #=< A, 204 A #=< L. 205 206iblock_nomatch(A, block{base: B, limit: L}) :- 207 A #< B ; 208 A #> L. 209 210iblocks_match_any(A, [B | Bs]) :- 211 iblock_match(A, B) ; iblocks_match_any(A, Bs). 212 213iblocks_match_any_ic(A, B) :- 214 iblocks_match_any(A,B), 215 labeling([A]). 216 217% Union of blocks. [block{base:0,limit:5},block{base:33,limit:35}] -> 0,1,..,5,33,..,35 218iblock_values(Blocks, Values) :- 219 findall(X, iblocks_match_any_ic(X, Blocks), Values). 220 221 222iblocks_match([], []). 223iblocks_match([A|As], [B|Bs]) :- 224 iblock_match(A,B), 225 iblocks_match(As, Bs). 226 227iblocks_nomatch([], []). 228iblocks_nomatch([A|As], [B|Bs]) :- 229 iblock_nomatch(A,B), 230 iblocks_nomatch(As, Bs). 231 232 233% For a ic constrained variable 234iblocks_match_ic(X,Bs) :- 235 length(Bs,LiLe), 236 length(X,LiLe), 237 iblocks_match(X, Bs), 238 labeling(X). 239 240% Cross product of blocks 241iblock_crossp(Blocks, Values) :- 242 findall(X, iblocks_match_ic(X, Blocks), Values). 243 244 245address_match([K, IAddr], [K, IBlocks]) :- 246 iblock_match(IAddr, IBlocks). 247 248address_match_region(Addr, region{blocks:Blocks}) :- 249 address_match(Addr, Blocks). 250 251iaddress_gt(S, B) :- 252 S #< B. 253 254% Will only compare addresses of the same kind 255address_gt([K, ISmaller], [K, IBigger]) :- 256 iaddress_gt(ISmaller, IBigger). 257 258% Will only compare addresses of the same kind 259address_gte([K, ISmaller], [K, IBigger]) :- 260 ISmaller #=< IBigger. 261 262% A - B = C ---> address_sub(A,B,C) 263address_sub([K, IA], [K, IB], [K, IC]) :- 264 IC is IA - IB. 265 266% A + B = C ---> address_add(A,B,C) 267address_add([K, IA], [K, IB], [K, IC]) :- 268 IC is IA + IB. 269 270% A + B = C ---> address_add(A,B,C) 271address_add_const_ic([K, IA], B, [K, IC]) :- 272 IC #= IA + B. 273 274% A + B = C ---> address_add(A,B,C) 275address_add_const([K, IA], B, [K, IC]) :- 276 IC is IA + B. 277 278address_var([K, IA]) :- 279 var(K) ; var(IA). 280 281iblock_iaddress_gt(Block, Addr) :- 282 block{ 283 limit: Limit 284 } = Block, 285 Addr #> Limit. 286 287block_address_gt([K, IBlocks], [K, IAddress]) :- 288 iblock_iaddress_gt(IBlocks, IAddress). 289 290 291block_block_contains([K, A], [K, B]) :- 292 A = block{base:ABase, limit: ALimit}, 293 B = block{base:BBase, limit: BLimit}, 294 ABase >= BBase, 295 ABase =< BLimit, 296 ALimit >= BBase, 297 ALimit =< BLimit. 298 299% region_region_contains(A,B) --> A is part of B 300region_region_contains(region{node_id:N, blocks:AB}, region{node_id:N, blocks:BB}) :- 301 block_block_contains(AB, BB). 302 303iblock_iblock_intersection(A, B, I) :- 304 A = block{base:ABase, limit: ALimit}, 305 B = block{base:BBase, limit: BLimit}, 306 % Case 4: B contained entirely in B. 307 (((ABase =< BBase, BLimit =< ALimit) -> I = B) ; 308 ( 309 % Case 1: A contained entirely in B. 310 (((BBase =< ABase, ALimit =< BLimit) -> I = A) ; 311 ( 312 % Case 2: B overlaps on the right of A. BBase in A. 313 (ABase =< BBase, BBase =< ALimit, I = block{base: BBase, limit: ALimit}) ; 314 315 % Case 3: B overlaps on the left of A. BLimit in A 316 (ABase =< BLimit, BLimit =< ALimit, I = block{base: ABase, limit: BLimit}) 317 )))). 318 319block_block_intersection([K, IABlock], [K, IBBlock], [K, ISBlock]) :- 320 iblock_iblock_intersection(IABlock, IBBlock, ISBlock). 321 322region_region_intersection(region{node_id:N, blocks:AB}, region{node_id:N, blocks:BB}, Is) :- 323 block_block_intersection(AB, BB, BIs), 324 Is = region{node_id: N, blocks: BIs}. 325 326:- export test_region_region_intersection/0. 327test_region_region_intersection :- 328 A1 = region{node_id:["ID"], blocks:[memory, block{base: 50, limit: 100}]}, 329 B1 = region{node_id:["ID"], blocks:[memory, block{base: 0, limit: 200}]}, 330 region_region_intersection(A1,B1,A1), 331 A2 = region{node_id:["ID"], blocks:[memory, block{base: 50, limit: 100}]}, 332 B2 = region{node_id:["ID"], blocks:[memory, block{base: 75, limit: 200}]}, 333 I2 = region{node_id:["ID"], blocks:[memory, block{base: 75, limit: 100}]}, 334 region_region_intersection(A2,B2,I2), 335 A3 = region{node_id:["ID"], blocks:[memory, block{base: 50, limit: 100}]}, 336 B3 = region{node_id:["ID"], blocks:[memory, block{base: 0, limit: 75}]}, 337 I3 = region{node_id:["ID"], blocks:[memory, block{base: 50, limit: 75}]}, 338 region_region_intersection(A3,B3,I3), 339 A4 = region{node_id:["ID"], blocks:[memory, block{base: 0, limit: 100}]}, 340 B4 = region{node_id:["ID"], blocks:[memory, block{base: 50, limit: 70}]}, 341 region_region_intersection(A4,B4,B4), 342 A5 = region{node_id:["ID"], blocks:[memory, block{base: 0, limit: 100}]}, 343 B5 = region{node_id:["ID"], blocks:[memory, block{base: 200, limit: 300}]}, 344 not(region_region_intersection(A5,B5,_)). 345 346 347% Calculates PartSrcRegion and PartSrc Name, such that PartSrcRegion is the 348% intersection between Src and FullSrcRegion. 349intersecting_translate_block(Src, FullSrcRegion, FullSrcName, PartSrcRegion, PartSrcName) :- 350 Src = region{}. 351 352% Turn the limit of the blocks into an address 353block_limit_address([K, Block], [K, Addr]) :- 354 block{ 355 limit: Addr 356 } = Block. 357 358% Turn the base of the blocks into an address 359block_base_address([K, Block], [K, Addr]) :- 360 (var(IBlocks), var(IAddress), fail) ; 361 block{ 362 base: Addr 363 } = Block. 364 365% Turn a region into a base name 366region_base_name(Region, Name) :- 367 Region = region{node_id: NodeId, blocks: Blocks}, 368 Name = name{node_id:NodeId, address: Base}, 369 block_base_address(Blocks, Base). 370 371% Turn a region into a limit name 372region_limit_name(Region, Name) :- 373 Region = region{node_id: NodeId, blocks: Blocks}, 374 block_limit_address(Blocks, Base), 375 Name = name{node_id:NodeId, address: Base}. 376 377block_size([K, A], [K, B]) :- 378 block{ 379 base: Base, 380 limit: Limit 381 } = A, 382 ( 383 (var(Limit), Limit is Base + B - 1) ; 384 (B is Limit - Base + 1) 385 ). 386 387region_size(Region, Size) :- 388 region{ blocks: Blocks } = Region, 389 block_size(Blocks, Size). 390 391regions_size([], 0). 392regions_size([Region | Regions], Size) :- 393 region_size(Region, [_, A]), 394 regions_size(Regions, B), 395 Size is A + B. 396 397iaddr_iblock_map(SrcAddr, SrcBlock, DstAddr, DstBase) :- 398 SrcBlock = block{base:SrcBase}, 399 DstAddr #= SrcAddr - SrcBase + DstBase. 400 401test_iaddr_iblock_map :- 402 iaddr_iblock_map([1],[block{base:0, limit:1024}], Dst, [100]), 403 Dst = [101]. 404 405%% Convert from region (encoded as block) to names 406region_name_match(Region,Name) :- 407 region{ 408 node_id:Id, 409 blocks: Blocks % Blocks = [Kind, block{...}] 410 } = Region, 411 address_match(Addr, Blocks), 412 Name = name{ 413 node_id:Id, 414 address:Addr 415 }. 416 417default_iaddr_constraint(Addr) :- 418 Addr #>= 0, 419 Addr #< 2147483648. 420 421%% Thes functions turn an IC constrained Addr to base/limit blocks 422iaddr_to_iblock_one(Addr, Block) :- 423 default_iaddr_constraint(Addr), 424 get_bounds(Addr,Min,Max), 425 Size is Max - Min + 1, 426 ( get_domain_size(Addr,Size) -> 427 Block = block{ 428 base:Min, 429 limit:Max 430 } 431 ; 432 writeln(stderr,"Name conversion to region failed: Non continuous domain for address"), 433 fail 434 ). 435 436addr_to_blocks([K, IAddr], [K, IBlocks]) :- 437 iaddr_to_iblock_one(IAddr, IBlocks). 438 439%% Convert from names to regions 440 441to_region(Name,Region) :- 442 name{ 443 node_id:Id, 444 address:Addr 445 } = Name, 446 region{ 447 node_id: Id, 448 blocks: Blocks 449 } = Region, 450 addr_to_blocks(Addr, Blocks). 451 452 453 454% block_translate(A,BaseA,B,BaseB) ==> A-BaseA = B-BaseB 455block_translate([SrcK, ISrcAddr], [SrcK, SrcBlock], [DstK, IDstAddr], [DstK, IDstBase]) :- 456 iaddr_iblock_map(ISrcAddr, SrcBlock, IDstAddr, IDstBase). 457 458test_block_translate :- 459 block_translate( 460 [memory,[1]], 461 [memory, [block{base:0, limit:1024}]], 462 Dst, 463 [memory, [100]]), 464 Dst = [memory, [101]]. 465 466%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 467%%%% Queries (that query the model layer) 468%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 469 470accept_name(S, Name) :- 471 name{ 472 node_id:NodeId, 473 address:Addr 474 } = Name, 475 CandidateRegion = region{node_id: NodeId}, 476 state_query(S, accept(CandidateRegion)), 477 address_match_region(Addr, CandidateRegion). 478 479 480accept_region(S, Region) :- 481 Region = region{node_id: RId}, 482 CandidateRegion = region{node_id: RId}, 483 state_query(S, accept(CandidateRegion)), 484 region_region_contains(Region, CandidateRegion). 485 486accept_regions(S, []). 487accept_regions(S, [R | Rs]) :- 488 accept_region(S, R), 489 accept_regions(S, Rs). 490 491accept_or_hole_regions(S, []). 492accept_or_hole_regions(S, [R | Rs]) :- 493 (accept_region(S, R) ; is_hole(R)), 494 accept_or_hole_regions(S, Rs). 495 496test_accept_name :- 497 S = [accept(region{node_id:["In"], blocks: [memory, block{base: 50, limit:100}]})], 498 accept_name(S, name{node_id:["In"], address: [memory, 75]}). 499 500test_accept_region :- 501 S = [accept(region{node_id:["In"], blocks: [memory, block{base: 50, limit:100}]})], 502 accept_region(S, region{node_id:["In"], blocks: [memory, block{base:75, limit:80}]}). 503 504decode_step_name(S, SrcName, name{node_id: DstId, address: DstAddr}) :- 505 translate(S, SrcRegion, name{node_id: DstId, address: DstBaseAddr}), 506 region_name_match(SrcRegion, SrcName), 507 SrcRegion = region{blocks:SrcBlocks}, 508 SrcName = name{address:SrcAddr}, 509 block_translate(SrcAddr, SrcBlocks, DstAddr, DstBaseAddr). 510 511%% We represent holes in the resolved set as region with node_id = hole 512hole_region(region{node_id: hole, blocks: Bs}, region{blocks: Bs}). 513is_hole(R) :- R = region{node_id: hole}. 514 515%% Translate SrcRegion into DstRegion using the InCandidate :: region and 516%% OutCandidate :: name, 517%% Only works if the SrcRegion is completly contained in the InCandidate, which 518%% is ensured by decode_step_region_part. 519decode_step_region_matching(S, InCandidate, OutCandidate, SrcRegion, DstRegion) :- 520 region_region_contains(SrcRegion, InCandidate), 521 region_base_name(SrcRegion, name{address:SrcAddr}), 522 InCandidate = region{blocks:InBlocks}, 523 OutCandidate = name{node_id: OutNodeId, address: DstBaseAddr}, 524 block_translate(SrcAddr, InBlocks, DstAddr, DstBaseAddr), 525 region_base_name(DstRegion, name{node_id: OutNodeId, address: DstAddr}), 526 region_size(SrcRegion, Size), 527 region_size(DstRegion, Size). 528 529% This recursion iterates over all translate blocks. If they match 530% the srcRegion, it will split the hole (which has to be found at this 531% point in DstCurr) 532decode_step_region_part(_, _, X, X, []). 533decode_step_region_part(S, SrcRegion, DstCurr, DstEnd, [(In,Out) | Tlx]) :- 534 (foreach(Dst, DstCurr), param(SrcRegion), param(In), param(Out), param(S), 535 fromto([], NewDstIn, NewDstOut, DstNext) do 536 Dst = region{node_id: hole, blocks: DstBlocks}, 537 SrcRegion = region{node_id: SrcRegionId}, 538 DstInSrc = region{node_id: SrcRegionId, blocks: DstBlocks}, 539 region_region_intersection(In, DstInSrc, Is) -> ( 540 Is = region{blocks: [_, block{base:IsB, limit: IsL}]}, 541 SrcRegion = region{blocks: [_, block{base:SrcB, limit: SrcL}]}, 542 IsBBefore is IsB - 1, 543 IsLAfter is IsL + 1, 544 HoleLeft = region{node_id: hole, blocks: [_, block{base: SrcB, limit: IsBBefore}]}, 545 decode_step_region_matching(S, In, Out, Is, Overlap), 546 HoleRight = region{node_id: hole, blocks: [_, block{base: IsLAfter, limit: SrcL}]}, 547 append(NewDstIn, [HoleLeft, Overlap, HoleRight], NewDstOut) 548 ) ; ( 549 append(NewDstIn, [Dst], NewDstOut) 550 ) 551 ), 552 decode_step_region_part(S, SrcRegion, DstNext, DstEnd, Tlx). 553 554% TODO: This function has to take accepting regions into account and not 555% try to translate them further. 556decode_step_region(S, SrcRegion, NextRegions) :- 557 findall((In,Out), translate(S, In, Out), Tlx), 558 hole_region(SrcHole, SrcRegion), 559 decode_step_region_part(S, SrcRegion, [SrcHole], NextRegionsTmp, Tlx), 560 (foreach(Reg, NextRegionsTmp), 561 fromto([], NewDstIn, NewDstOut, NextRegions) do 562 ((not(is_hole(Reg)) -> append(NewDstIn, [Reg], NewDstOut)) ; ( 563 Reg = region{blocks: [_, block{base:B, limit: L}]}, 564 (L >= B) -> append(NewDstIn, [Reg], NewDstOut) ; NewDstOut = NewDstIn 565 ) 566 )). 567 568% Like decode_step_region, but consider additional configuration entries. 569% TODO: Only works if SrcRegion matches exactly a Configuration block. 570% This function uses IC internally,but labels the outputs. 571decode_step_region_conf_one(S, SrcRegion, DstRegion, Confs) :- 572 SrcRegion = region{node_id: SrcId, blocks: [Kind, block{base: SrcB, limit: SrcL}]}, 573 state_query(S, block_meta(SrcId, Bits, OutNodeId)), 574 575 % Make sure base address is aligned 576 iaddress_aligned(SrcB, Bits), 577 DstRegion = region{node_id: OutNodeId, blocks: [Kind, block{base: DestB, limit: DestL}]}, 578 579 % Make sure Input Size is multiple of BlockSize 580 region_size(SrcRegion, [_, RSize]), 581 BlockSize is 2^Bits, 582 BlockNum #>= 0, 583 RSize #= BlockNum * BlockSize, 584 585 % Get base VPN/PPN pair 586 split_vaddr(SrcB, Bits, [BaseVPN, Offset]), 587 split_vaddr(DestB, Bits, [BasePPN, Offset]), 588 DestL #= DestB + RSize - 1, 589 labeling([BasePPN, BaseVPN]), 590 591 % Consecutive VPN PPN pairs 592 ItEnd is BlockNum - 1, 593 (for(I,0,ItEnd), fromto([], In, Out, Confs), 594 param(BaseVPN), param(BasePPN), param(SrcId) do 595 NVPN is I + BaseVPN, 596 NPPN is I + BasePPN, 597 append(In, [block_conf(SrcId, NVPN, NPPN)], Out) 598 ). 599 600decode_step_region_conf(S, SrcRegion, DstRegions, Confs) :- 601 % TODO: WIP 602 SrcRegion = region{node_id: SrcId, blocks: [Kind, block{base: SrcB, limit: SrcL}]}, 603 state_query(S, block_meta(SrcId, Bits, OutNodeId)), 604 Size is 2^Bits, 605 split_region(SrcRegion, Size, SplitSrc), 606 (foreach(Src, SplitSrc), 607 fromto([],DstIn,DstOut,DstRegions), 608 fromto([],ConfsIn,ConfsOut,Confs), 609 param(S) do 610 decode_step_region_conf_one(S, Src, Dst, ConfsPart), 611 append(DstIn, [Dst], DstOut), 612 append(ConfsIn, ConfsPart, ConfsOut) 613 ). 614 615split_region(Region, Size, Splits) :- 616 % TODO IMPLEMENT ME 617 Splits = [Region]. 618 619test_split_region :- 620 InR = region{node_id:["IN"], blocks: [memory, block{base:0, limit: 8}]}, 621 Size = 4, 622 split_region(InR, Size, Out). 623 624test_decode_step_region_conf_one :- 625 S = [block_meta(["IN"], 21, ["OUT"])], 626 Base = 0, 627 Limit is Base + 2^21 - 1, 628 SrcRegion = region{node_id: ["IN"], blocks: [memory, block{base:Base, limit:Limit}]}, 629 decode_step_region_conf_one(S, SrcRegion, Out1, [Conf1]), 630 631 TestBase is 512 * 2^21, 632 Out2 = region{node_id:["OUT"], blocks: [memory, block{base:TestBase}]}, 633 decode_step_region_conf_one(S, SrcRegion, Out2, [Conf2]), 634 Conf2 = block_conf(["IN"], 0, 512), 635 636 % Try multiple of Bits 637 Base3 = 0, 638 Limit3 is Base3 + 2^23 - 1, 639 SrcRegion3 = region{node_id: ["IN"], blocks: [memory, block{base:Base3, limit:Limit3}]}, 640 decode_step_region_conf_one(S, SrcRegion3, Out3, Confs3), 641 Confs3 = [ 642 block_conf(["IN"], 0, 0), 643 block_conf(["IN"], 1, 1), 644 block_conf(["IN"], 2, 2), 645 block_conf(["IN"], 3, 3)]. 646 647 648 649:- export test_decode_step_region_conf2/0. 650test_decode_step_region_conf2 :- 651 S = [block_meta(["IN"], 21, ["OUT"])], 652 Base = 0, 653 Limit is Base + 2^22 - 1, % Note the second 2 in 22, this remaps two blocks 654 SrcRegion = region{node_id: ["IN"], blocks: [memory, block{base:Base, limit:Limit}]}, 655 decode_step_region_conf(S, SrcRegion, [Out1], Conf1), 656 printf("Out1 (free)=%p, Conf1=%p\n",[Out1, Conf1]). 657 %TestBase is 512 * 2^21, 658 %Out2 = region{node_id:["OUT"], blocks: [memory, block{base:TestBase}]}, 659 %decode_step_region_conf(S, SrcRegion, [Out2], Conf2), 660 %%printf("Out2 (fixed)=%p, Conf2=%p\n",[Out2, Conf2]), 661 %Conf2 = [block_conf(["IN"], 0, 512)]. 662 663decode_step_regions(S, [], []). 664decode_step_regions(S, [A | As], Regs) :- 665 decode_step_region(S, A, RegsA), 666 decode_step_regions(S, As, RegsB), 667 append(RegsA, RegsB, Regs). 668 669decode_step_regions_conf(S, [], [], []). 670decode_step_regions_conf(S, [A | As], Regs, Conf) :- 671 decode_step_region_conf(S, A, RegsA, ConfA), 672 decode_step_regions_conf(S, As, RegsB, ConfB), 673 append(RegsA, RegsB, Regs), 674 append(ConfA, ConfB, Conf). 675 676test_decode_step_region1 :- 677 % The simple case: everything falls into one translate block 678 S = [ 679 mapping( 680 region{node_id: ["IN"], blocks: [memory, block{base:0, limit:100}]}, 681 name{node_id: ["OUT1"], address: [memory, 10]}), 682 mapping( 683 region{node_id: ["IN"], blocks: [memory, block{base:200, limit:300}]}, 684 name{node_id: ["OUT2"], address: [memory, 200]}) 685 ], 686 687 decode_step_region(S, 688 region{node_id:["IN"], blocks: [memory, block{base:50, limit: 70}]}, 689 Out1), 690 Out1 = [region{node_id:["OUT1"], blocks: [memory, block{base:60, limit: 80}]}], 691 692 decode_step_region(S, 693 region{node_id:["IN"], blocks: [memory, block{base:50, limit: 199}]}, 694 Out2), 695 Out2 = [region{node_id:["OUT1"], blocks: [memory, block{base:60, limit: 110}]}, 696 Hole2], 697 region_size(Hole2, [_, 99]), 698 699 decode_step_region(S, 700 region{node_id:["IN"], blocks: [memory, block{base:50, limit: 200}]}, 701 Out3), 702 Out3 = [ 703 region{node_id:["OUT1"], blocks: [memory, block{base:60, limit: 110}]}, 704 _, 705 region{node_id:["OUT2"], blocks: [memory, block{base:200, limit: 200}]} 706 ], 707 decode_step_region(S, 708 region{node_id:["IN"], blocks: [memory, block{base:150, limit: 350}]}, 709 Out4), 710 Out4 = [_, region{node_id:["OUT2"], blocks: [memory, block{base:200, limit: 300}]}, _]. 711 712test_decode_step_region2 :- 713 % The simple case: everything falls into one translate block 714 S = [ 715 mapping( 716 region{node_id: ["IN"], blocks: [memory, block{base:0, limit:100}]}, 717 name{node_id: ["OUT"], address: [memory, 1]}) 718 ], 719 720 decode_step_region(S, 721 region{node_id:["IN"], blocks: [memory, block{base:50, limit: 70}]}, 722 Out), 723 Out = [region{node_id:["OUT"], blocks: [memory, block{base:51, limit: 71}]}]. 724 725test_decode_step_region3 :- 726 % Complicated case, overlapping translate 727 S = [ 728 mapping( 729 region{node_id: ["IN"], blocks: [memory, block{base:0, limit:100}]}, 730 name{node_id: ["OUT1"], address: [memory, 10]}), 731 mapping( 732 region{node_id: ["IN"], blocks: [memory, block{base:200, limit:300}]}, 733 name{node_id: ["OUT2"], address: [memory, 20]}), 734 mapping( 735 region{node_id: ["IN"], blocks: [memory, block{base:400, limit:500}]}, 736 name{node_id: ["OUT3"], address: [memory, 30]}) 737 ], 738 739 decode_step_region(S, 740 region{node_id:["IN"], blocks: [memory, block{base:50, limit: 450}]}, 741 Out). 742 %printf("decode_step_region returns %p\n", [Out]). 743 744:- export test_decode_step_name/0. 745test_decode_step_name :- 746 S = [mapping( 747 region{ 748 node_id: ["IN"], 749 blocks: [memory, block{base:0, limit:100}] 750 }, 751 name{node_id: ["OUT"], address: [memory, 1]})], 752 753 decode_step_name(S, 754 name{node_id:["IN"], address: [memory, 1]}, 755 name{node_id:OutNodeId, address: OutAddr}), 756 OutNodeId = ["OUT"], 757 OutAddr = [memory, 2]. 758 759:- export test_decode_step_name2/0. 760test_decode_step_name2 :- 761 %Setup 762 S = [ 763 mapping( 764 region{node_id:["In"], blocks:[memory, block{base:1000,limit:2000}]}, 765 name{node_id: ["Out1"], address: [memory, 0]}), 766 overlay(["In"], ["Out2"]) 767 ], 768 % Test the translate block 769 decode_step_name(S, 770 name{node_id:["In"], address:[memory, 1000]}, 771 name{node_id:["Out1"], address: [memory, 0]} 772 ), 773 % Test the overlay 774 decode_step_name(S, 775 name{node_id:["In"], address:[memory, 0]}, 776 name{node_id:["Out2"], address:[memory, 0]} 777 ), 778 % make sure the upper limit is respected. 779 decode_step_name(S, 780 name{node_id:["In"], address: [memory, 2500]}, 781 name{node_id:["Out2"], address: [memory, 2500]}), 782 % make sure no within block translation to overlay exists 783 not(decode_step_name(S, 784 name{node_id: ["In"], address: [memory, 1000]}, 785 name{node_id: ["Out2"], address: [memory, 1000]})). 786 787:- export test_decode_step_name3/0. 788test_decode_step_name3 :- 789 %Setup 790 S = [ 791 mapping( 792 region{node_id:["In"], blocks:[memory, block{base:1000,limit:2000}]}, 793 name{node_id: ["Out1"], address: [memory, 0]}), 794 mapping( 795 region{node_id:["In2"], blocks:[memory, block{base:2000,limit:3000}]}, 796 name{node_id: ["Out1"], address: [memory, 0]}), 797 overlay(["In"], ["Out2"]) 798 ], 799 % Test the translate block 800 Src = name{node_id:["In"]}, 801 decode_step_name(S, 802 Src, 803 name{node_id:["Out1"], address: [memory, 0]} 804 ), 805 Src = name{node_id:["In"], address: [memory, 1000]}. 806 807 808% Reflexive, transitive closure of decode_step_* 809:- export decodes_name/3. 810decodes_name(_, N,N). 811decodes_name(S, SrcName, DstName) :- 812 decode_step_name(S, SrcName, NextName), 813 decodes_name(S, NextName, DstName). 814 815:- export resolve_name/3. 816resolve_name(S, SrcName, DstName) :- 817 name{} = SrcName, 818 name{} = DstName, 819 decodes_name(S, SrcName,DstName), 820 accept_name(S, DstName). 821 822decodes_regions(_, N, N). 823decodes_regions(S, SrcRegions, DstRegions) :- 824 decode_step_regions(S, SrcRegions, NextRegions), 825 decodes_regions(S, NextRegions, DstRegions). 826 827resolve_regions(S, SrcRegions, DstRegions) :- 828 decodes_regions(S, SrcRegions, DstRegions), 829 accept_regions(S, DstRegions). 830 831:- export test_resolve_name/0. 832test_resolve_name :- 833 %Setup 834 S = [ 835 mapping( 836 region{node_id:["In"], blocks: [memory, block{base:1000,limit:2000}]}, 837 name{node_id: ["Out1"], address : [memory, 0]}), 838 overlay(["In"], ["Out2"]), 839 accept(region{node_id:["Out1"], blocks: [memory,block{base:0, limit:2000}]}), 840 accept(region{node_id:["Out2"], blocks: [memory,block{base:0, limit:2000}]}) 841 ], 842 % Hit the translate block 843 resolve_name(S, 844 name{node_id:["In"], address:[memory, 1000]}, 845 name{node_id:["Out1"], address:[memory, 0]}), 846 % Hit the overlay 847 resolve_name(S, 848 name{node_id:["In"], address:[memory, 500]}, 849 name{node_id:["Out2"], address:[memory, 500]}). 850 851test_resolve_name2 :- 852 %Setup 853 S = [mapping( 854 region{node_id: ["In1"], blocks: [memory, block{base:1000,limit:2000}]}, 855 name{node_id: ["Out1"], address: [memory, 0]}), 856 mapping( 857 region{node_id:["In2"], blocks:[memory, block{base:6000,limit:7000}]}, 858 name{node_id:["Out1"], address: [memory, 0]}), 859 accept(region{node_id:["Out1"], blocks: [memory, block{base:0, limit:2000}]}) 860 ], 861 % Reverse lookup 862 resolve_name(S, 863 name{node_id:["In1"], address:[memory, 1000]}, 864 R), 865 resolve_name(S, 866 name{node_id:["In2"], address:Out}, 867 R), 868 Out = [memory, 6000]. 869 870test_resolve3(Out) :- 871 %Setup 872 assert(node_translate_dyn( 873 ["In1"], [memory, [block{base:1000,limit:2000}]], 874 ["Out1"], [memory, [block{base:0,limit:1000}]])), 875 assert(node_translate_dyn( 876 ["In2"], [memory, [block{base:6000,limit:7000}]], 877 ["Out1"], [memory, [block{base:0,limit:1000}]])), 878 assert(node_accept(["Out1"], [memory,[block{base:0, limit:2000}]])), 879 InRegion = region{node_id:["In1"], blocks:[memory, block{base:1000, limit:1500}]}, 880 resolve(InRegion,Out). 881 882 883%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 884%%%% Load sockeye compiled decoding nets and instantiate modules 885%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 886:- export load_net/1. 887load_net(File) :- 888 ensure_loaded(File). 889 890:- export load_module/2. 891load_module(Mod, Id) :- 892 call(Mod, Id). 893 894:- export load_net_module/2. 895load_net_module(File, Mod) :- 896 ensure_loaded(File), 897 call(Mod, []). 898 899%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 900%%%% Node enumeration. 901%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 902 903:- export alloc_node_enum/1. 904:- dynamic enum_node_id/2. 905:- export enum_node_id/2. 906alloc_node_enum(N) :- alloc_one(node_enum, N). 907 908get_or_alloc_node_enum(NodeId, Enum) :- 909 enum_node_id(Enum, NodeId) ; 910 ( alloc_node_enum(Enum), assert(enum_node_id(Enum, NodeId)) ). 911 912 913%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 914%%%% VNode Allocator. 915%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 916 917:- dynamic vnode_region/1. 918 919vnode_meta(PageSize, PoolSize) :- 920 PageSize is 2 ^ 12, % 4Kb Pages 921 PoolSize is 2048. % Number of pages 922 923% TODO: Test me 924vnode_alloc(BaseAddr) :- 925 vnode_region(Reg), 926 region_base_name(Reg, RegName), 927 alloc_one(vnodes, Slot), 928 vnode_meta(PageSize,_), 929 RegName = name{address: Addr}, 930 Offset is PagesSize * Slot, 931 address_add_const(Addr, Offset, NewAddr), 932 NewAddr = [memory, [BaseAddr]]. 933 934 935%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 936%%%% X86 Support. Complements the sockeye file, should really be moved into its own file 937%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 938 939:- export init/0. 940:- export add_pci_alloc/1. 941:- export add_pci/1. 942:- export add_process/1. 943:- export add_process_alloc/1. 944:- export dram_nodeid/1. 945:- export alloc_root_vnodeslot/2. 946:- export free_root_vnodeslot/2. 947 948:- dynamic pci_address_node_id/2. 949:- export pci_address_node_id/2. 950:- dynamic process_node_id/2. 951:- export process_node_id/2. 952 953alloc_root_vnodeslot(NodeId, Slot) :- 954 alloc_one(root_vnodeslot(NodeId), Tmp), 955 Slot is Tmp + 2. 956 957free_root_vnodeslot(NodeId, Slot) :- 958 Tmp is Slot - 2, 959 free_one(root_vnodeslot(NodeId), Tmp). 960 961dram_nodeid(NodeId) :- NodeId = ["DRAM"]. 962 963% This uses the memory_region facts (defined in the main module) to 964% find a region above 4G that we will manage. 965initial_dram_block(Block) :- %a 966 % Find the usable DRAM using the existing SKB facts 967 call(mem_region_type, RamType, ram)@eclipse, 968 findall((Base, Size), call(memory_region,Base,Bits,Size,RamType,Data)@eclipse, MemCandidates), 969 (foreach((Base,Size), MemCandidates), fromto([], In, Out, FiltCandidates) do 970 (((MinBase = 4294967296, % 4G 971 MinSize = 1073741824, % 1G 972 Base >= MinBase, 973 Size >= MinSize) -> Out = [(Base,Size) | In] 974 ) ; ( 975 Out = In 976 )) 977 ), 978 FiltCandidates = [(Base,Size) | _], 979 Limit is Base + Size, 980 Block = block{base:Base, limit: Limit}. 981 982 983init(NewS) :- 984 state_empty(S1), 985 add_SYSTEM([]), 986 DRAM_ID = ["DRAM"], 987 initial_dram_block(Block), 988 state_add(S1, accept(["DRAM"], [memory, [Block]]), S2), 989 get_or_alloc_node_enum(S2, DRAM_ID, DRAM_ENUM, S3), 990 printf("Decoding net initialized using %p as DRAM. DRAM nodeid: %p\n", 991 [Block, DRAM_ENUM]), 992 993 % Manage space for vnodes 994 vnode_meta(PageSize, PoolSize), 995 VnodePoolSize is PageSize * PoolSize, 996 Size = [VnodePoolSize], 997 alloc_range(S2, DRAM_ID, [memory, Size], BaseOut, S3), 998 mark_range_in_use(S3, DRAM_ID, BaseOut, Size, S4), 999 in_use(DRAM_ID, Region), 1000 assert(vnode_region(Region)), 1001 writeln("Using for PageTables:"), writeln(Region). 1002 1003add_pci(S, NewS) :- 1004 add_pci(S, ["PCI0"], addr(0,0,0), NewS). 1005 1006iommu_enabled :- 1007 call(iommu_enabled,0,_)@eclipse. 1008 1009add_pci(S0, Id, Addr, NewS) :- 1010 Addr = addr(_,_,_), 1011 PCIBUS_ID = ["PCIBUS"], 1012 PCIIN_ID = ["IN" | Id], 1013 PCIOUT_ID = ["OUT" | Id], 1014 (iommu_enabled -> ( 1015 add_PCI_IOMMU(S0, Id, S1), 1016 % Mark IOMMU block remappable 1017 state_add(S1, block_meta(["IN", "IOMMU0" | Id], 21, ["OUT", "IOMMU0" | Id]), S2) 1018 %% And assign a root PT 1019 %pt_alloc(Root), 1020 %assert(node_pt(["IN", "IOMMU0", Id], Root, ["OUT","IOMMU0",Id])) 1021 ) ; ( 1022 % IOMMU disabled. 1023 add_PCI(S0, Id, S2) 1024 )), 1025 1026 % connect the output to the systems pci bus 1027 state_add(S2, overlay(PCIOUT_ID, PCIBUS_ID), S3), 1028 1029 % Now insert the BAR into the PCI bus address space 1030 findall((Addr, BarNum, BarStart, BarSize), 1031 call(bar(Addr, BarNum, BarStart, BarSize, mem, _, _))@eclipse, 1032 Bars), 1033 (foreach((_, BarNum, BarStart, BarSize), Bars), 1034 param(Id), param(PCIBUS_ID), 1035 fromto(S3, SIn, SOut, NewS) do 1036 BarId = [BarNum, "BAR" | Id], 1037 BarEnd is BarStart + BarSize, 1038 state_add(SIn, accept(region{ 1039 node_id: BarId, 1040 blocks: [memory, block{base:BarStart,limit:BarEnd}]}), SIn1), 1041 state_add(SIn1, 1042 mapping(region{ 1043 node_id: PCIBUS_ID, 1044 blocks: [memory,block{base:BarStart,limit:BarEnd}] 1045 }, 1046 name{ 1047 node_id: BarId, 1048 address: [memory, BarStart] 1049 }), 1050 SOut) 1051 ). 1052 1053add_pci_alloc(S, Addr, NewS) :- 1054 alloc_node_enum(S, Enum, S1), 1055 add_pci(S1, [Enum], Addr, S2), 1056 % Set it to the node id where addresses are issued from the PCI device 1057 OutNodeId = ["OUT", "PCI0", Enum], 1058 state_add(S2, enum_node_id(Enum, OutNodeId), S3), 1059 state_add(S3, pci_address_node_id(Addr, Enum), NewS). 1060 1061add_process_alloc(S, Enum, NewS) :- 1062 alloc_node_enum(Enum), 1063 add_process([Enum]), 1064 % Set it to the node id where addresses are issued from the process 1065 assert(enum_node_id(Enum, ["OUT", "PROC0", Enum])). 1066 %assert(process_node_id(ProcId, Enum)). 1067 1068 1069% Make ID argument if we want to add multiple. 1070add_process(S, NewS) :- 1071 add_process(S, ["PROC0"], NewS). 1072 1073add_process(S, Id, NewS) :- 1074 DRAM_ID = ["DRAM"], 1075 add_PROC_MMU(S, Id, S1), 1076 1077 % Mark MMU block remappable 1078 MMU_IN_ID = ["IN", "MMU0" | Id], 1079 MMU_OUT_ID = ["OUT", "MMU0" | Id], 1080 state_add(S1, node_block_meta(MMU_IN_ID, 21, MMU_OUT_ID), S2), % Make MMU configurable 1081 %pt_alloc(S2, Root, S3), 1082 state_add(S2, node_pt(MMU_IN_ID, Root, MMU_OUT_ID), S4), 1083 1084 OUT_ID = ["OUT" | Id], 1085 state_add(S4, overlay(OUT_ID, DRAM_ID), S5), 1086 % Reserve memory for the process, the OUT/PROC0 node is the one where 1087 % initially the process (virtual) addresses are issued. 1088 Limit = 1099511627775, % (512 << 31) - 1 1089 state_add(S5, in_use(["OUT", "PROC0" | Id], [memory, [block{base:0, limit: Limit}]]), NewS). 1090 1091 1092 1093%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1094%%%% Mark ranges used and Query them 1095%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1096 1097% Puts IC constraints on the variables 1098free_region(S, NodeId, _, Out) :- 1099 % Not a very smart allocator, finds the highest addr in use and append 1100 % Therefore can ignore Size 1101 findall(X, state_query(S, in_use(NodeId, X)), UsedBlockLi), 1102 block_address_gt([memory, block{limit: -1}], Out), % TODO: Works only for 1 Dim addr. 1103 (foreach(UsedBlock, UsedBlockLi), param(Out) do 1104 block_address_gt(UsedBlock, Out) 1105 ). 1106 1107% Puts IC constraints on the variables 1108free_region(S, Name, Size) :- 1109 name{ 1110 node_id: NodeId, 1111 address: Out 1112 } = Name, 1113 free_region(S, NodeId, Size, Out). 1114 1115free_region(S, Region, Size) :- 1116 region_base_name(Region, Name), 1117 free_region(S, Name, Size). 1118 1119% Resolves the variables 1120free_region_aligned(S, Region, Size) :- 1121 is_list(Size), 1122 region_base_name(Region, BaseName), 1123 free_region(S, BaseName, Size), 1124 name_aligned(BaseName, 21), 1125 term_variables(BaseName, BaseNameVars), 1126 labeling(BaseNameVars), 1127 region_size(Region, Size). 1128 1129% Resolves the variables 1130free_accepted_region_aligned(S, Region, Size) :- 1131 is_list(Size), 1132 region_base_name(Region, BaseName), 1133 free_region(S, BaseName, Size), 1134 name_aligned(BaseName, 21), 1135 accept(BaseName), 1136 term_variables(BaseName, BaseNameVars), 1137 labeling(BaseNameVars), 1138 region_size(Region, Size). 1139 1140%:- export free_region/1. 1141%free_region(Region) :- 1142% region_size(Region, Size), % Determine size using the base/limit in the region. 1143% free_region(Region, Size). 1144 1145 1146%% NodeId:: Addr, Size :: Addr, Out :: Addr 1147alloc_range(S, NodeId, Size, Out) :- 1148 free_region(S, NodeId, Size, Out), 1149 term_variables(Out, OutVars), 1150 labeling(OutVars). 1151 1152 1153% After finding a range with alloc range, you actually want to mark it used 1154% with this function. 1155mark_range_in_use(S, NodeId, [Kind, A], Size, NewS) :- 1156 Limit is A + Size, 1157 UsedBlock = block{ 1158 base: A, 1159 limit: Limit 1160 }, 1161 state_add(S, in_use(NodeId, [Kind, UsedBlock]), NewS). 1162 1163mark_range_in_use(S, Name, ISize, NewS) :- 1164 name{ 1165 node_id: NodeId, 1166 address: Addr 1167 } = Name, 1168 mark_range_in_use(NodeId, Addr, ISize). 1169 1170mark_range_in_use(S, Region, NewS) :- 1171 Region = region{ node_id: NodeId, blocks: Blocks }, 1172 state_add(S, in_use(NodeId, Blocks), NewS). 1173 1174 1175mark_range_free(S, NodeId, Base, NewS) :- 1176 state_remove(S, in_use(NodeId, [memory, [block{base: Base}]]), NewS). 1177 1178:-export test_alloc_range/0. 1179test_alloc_range :- 1180 Id = [], 1181 state_empty(S), 1182 % Test setup 1183 mark_range_in_use(S, Id, [memory, 0], 1000, S1), 1184 1185 % First allocation 1186 Size = 1000, 1187 alloc_range(S1, Id, [memory, Size], Out), 1188 mark_range_in_use(S1, Id, Out, Size, S2), 1189 Out = [memory, 1001], 1190 1191 % Second allocation 1192 Size2 = 5000, 1193 alloc_range(S2, Id, [memory, Size2], Out2), 1194 mark_range_in_use(S2, Id, Out2, Size2, _), 1195 Out2 = [memory, 2002]. 1196 1197% Find a unused buffer, using already set up routing. 1198% Node1 :: Addr, Node2 :: Name, Resolved :: Name 1199common_free_buffer_existing(BufferSize, Node1, Node2, Resolved) :- 1200 free_region(Node1, [memory, [BufferSize]]), 1201 free_region(Node2, [memory, [BufferSize]]), 1202 resolve(Node1, Resolved), 1203 resolve(Node2, Resolved), 1204 free_region(Resolved, BufferSize), 1205 term_variables(Resolved, Vars), 1206 labeling(Vars). 1207 1208test_common_free_buffer_existing(Proc,Pci,Resolved) :- 1209 init, add_pci, add_process, 1210 BUFFER_SIZE = 1024, 1211 Proc = name{node_id: ["OUT", "PROC0", "PROC0"]}, 1212 Pci = name{node_id: ["OUT", "PCI0", "PCI0"]}, 1213 common_free_buffer_existing(BUFFER_SIZE, Proc, Pci, Resolved). 1214 1215% Like common_free_buffer_existing, but allow reconfiguration of nodes (routing) 1216% Find two regions N1Region and N2Region, that resolve to a free region. 1217:- export common_free_buffer/5. 1218common_free_buffer(Size, N1Region, N2Region, ResRegion, Route) :- 1219 is_list(Size), 1220 1221 N1Region = region{blocks: [memory, _]}, 1222 N2Region = region{blocks: [memory, _]}, 1223 ResRegion = region{blocks: [memory, block{base:Base, limit: Limit}]}, 1224 1225 % nail down the regions 1226 free_region_aligned(N1Region, Size), 1227 free_region_aligned(N2Region, Size), 1228 free_accepted_region_aligned(ResRegion, Size), 1229 accept(ResRegion), 1230 1231 route(N1Region, ResRegion, R1), 1232 route(N2Region, ResRegion, R2), 1233 1234 union(R1,R2,Route). 1235 1236% Find two regions N1Region and N2Region, that resolve to an existing result region. 1237:- export common_free_map/5. 1238common_free_map(Size, N1Region, N2Region, ResRegion,Route) :- 1239 is_list(Size), 1240 1241 N1Region = region{blocks: [memory, _]}, 1242 N2Region = region{blocks: [memory, _]}, 1243 ResRegion = region{blocks: [memory, block{base:Base, limit: Limit}]}, 1244 1245 % nail down the input regions first 1246 free_region_aligned(N1Region, Size), 1247 free_region_aligned(N2Region, Size), 1248 1249 route(N1Region, ResRegion, R1), 1250 route(N2Region, ResRegion, R2), 1251 1252 labeling([Base,Limit]), 1253 union(R1,R2,Route). 1254 1255% the function called from mem_serv 1256:- export alloc_common/4. 1257% Allocate a Buffer with Bits size, reachable from N1 and N2. Mark the resolved 1258% region as in use. 1259alloc_common(Bits, N1Enum, N2Enum, DestEnum) :- 1260 enum_node_id(N1Enum, N1Id), 1261 enum_node_id(N2Enum, N2Id), 1262 enum_node_id(DestEnum, DestId), 1263 R1 = region{node_id: N1Id, blocks: [memory, block{base:R1Addr}]}, 1264 R2 = region{node_id: N2Id, blocks: [memory, block{base:R2Addr}]}, 1265 Dest = region{node_id: DestId, blocks: [memory, block{base:DestAddr}]}, 1266 Size is 2 ^ Bits - 1, 1267 common_free_buffer([memory, [Size]], R1, R2, Dest, _), 1268 mark_range_in_use(Dest), 1269 writeln([name(R1Addr, N1Enum),name(R2Addr, N2Enum),name(DestAddr, DestEnum)]). 1270 1271% Like alloc_common/4, but tries to determine destination node automatically. 1272:- export alloc_common/3. 1273alloc_common(Bits, N1Enum, N2Enum) :- 1274 DRAM = ["DRAM"], 1275 get_or_alloc_node_enum(DRAM, DramEnum), 1276 alloc_common(Bits, N1Enum, N2Enum, DramEnum). 1277 1278% Find names in N1 and N2 that resolve to ResAddr, then mark those used. 1279:- export map_common/4. 1280map_common(Bits, ResRAddr, N1Enum, N2Enum) :- 1281 enum_node_id(N1Enum, N1Id), 1282 enum_node_id(N2Enum, N2Id), 1283 R1 = region{node_id: N1Id, blocks: [memory, block{base:R1Addr}]}, 1284 R2 = region{node_id: N2Id, blocks: [memory, block{base:R2Addr}]}, 1285 Size is 2 ^ Bits - 1, 1286 ResR = region{blocks: [memory, block{base:ResRAddr}]}, 1287 common_free_map([memory, [Size]], R1, R2, ResR, _), 1288 ResR = region{node_id: ResRId}, 1289 get_or_alloc_node_enum(ResRId, ResEnum), 1290 mark_range_in_use(R1), 1291 mark_range_in_use(R2), 1292 writeln([name(R1Addr, N1Enum),name(R2Addr, N2Enum),name(ResRAddr, ResEnum)]). 1293 1294 1295% Translate a name from one Node to a name to another node, so they 1296% resolve to the same ressource. 1297:- export change_view/2. 1298change_view(Name1, Name2) :- 1299 resolve(Name1, D), 1300 resolve(Name2, D). 1301 1302test_change_view(pci) :- 1303 init, add_pci, add_process, 1304 Proc = name{node_id: ["OUT", "PROC0", "PROC0"], address: [memory, [0]]}, 1305 Pci = name{node_id: ["OUT", "PCI0", "PCI0"]}, 1306 change_view(Proc, Pci). 1307 1308 1309%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1310%%%% Bit Array Representation 1311%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1312 1313array_all_eq([], _). 1314array_all_eq([A | Bs], A) :- array_all_eq(Bs,A). 1315array_all_eq(Arr, A) :- array_list(Arr, ArrLi), array_all_eq(ArrLi, A). 1316 1317% Constrains word to be a N bit word 1318assert_word(W, N) :- 1319 dim(W,[N]), W :: [0 .. 1]. 1320 1321% This beauty converts words (array of bit values) to a numeric representation. 1322word_to_num(W, Num) :- 1323 dim(W, [Len]), 1324 (for(I,1,Len), fromto(0,In,Out,NumT), param(W) do 1325 Out = W[I] * 2^(I-1) + In), 1326 Num $= eval(NumT). 1327 1328% A part of word is etracted into Subword, Range specifies 1329subword(Word,Subword, Range) :- 1330 SW is Word[Range], 1331 array_list(Subword,SW). 1332 1333 1334%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1335%%%% Block Remappable Nodes 1336%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1337 1338% As of now, block remappable implies that the node is one dimension 1339:- dynamic node_block_conf/3. %(NodeId, VPN, PPN). 1340:- dynamic node_block_meta/3. %(NodeId, BlockSizeBits, OutNodeId) 1341 1342% Translate using Block Conf. Same signature as node_translate 1343node_translate_block(InNodeId, [memory, [VAddr]], OutNodeId, [memory, [PAddr]]) :- 1344 node_block_meta(InNodeId, BlockSizeBits, OutNodeId), 1345 % Bit-Lookup Offset and VPN 1346 assert_word(VAW, 48), 1347 word_to_num(VAW, VAddr), 1348 subword(VAW, VAOffsetW, 1 .. BlockSizeBits), 1349 VPNStartBit is BlockSizeBits + 1, 1350 subword(VAW, VPNW, VPNStartBit .. 48), 1351 word_to_num(VPNW, VPN), 1352 1353 % Lookup PPN and PA offset 1354 node_block_conf(InNodeId, VPN, PPN), 1355 1356 % Stich together PA 1357 assert_word(PAW, 48), % TODO bit size for physical address? 1358 subword(PAW, VAOffsetW, 1 .. 21), 1359 subword(PAW, PPNW, 22 .. 48), 1360 word_to_num(PPNW, PPN), 1361 1362 word_to_num(PAW, PAddr). 1363 1364test_node_translate_block :- 1365 assert(node_block_conf([], 0, 1)), 1366 assert(node_block_meta([], 21, ["OUT"])), 1367 node_translate_block([], [memory,[1000]], ["OUT"], [memory, [2098152]]). 1368 1369 1370%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1371%%%% Routing 1372%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1373 1374one_block_upper_limit(Name, Limit) :- 1375 Name = name{ 1376 node_id: NodeId, 1377 address: Address 1378 }, 1379 (( % Block remappable? 1380 node_block_meta(NodeId, BlockSizeBits, _), 1381 Address = [K, [A]], 1382 Limit = [K, [ILimit]], 1383 assert_word(AW, 48), 1384 word_to_num(AW, A), 1385 assert_word(LimitW, 48), % TODO bit size for physical address? 1386 UpperStartBit is BlockSizeBits + 1, 1387 subword(AW, UpperW, UpperStartBit .. 48), 1388 subword(LimitW, UpperW, UpperStartBit .. 48), 1389 subword(LimitW, LowerW, 1 .. BlockSizeBits), 1390 array_all_eq(LowerW, 1), 1391 word_to_num(LimitW, ILimit) 1392 ) ; ( 1393 % In a translate block? 1394 node_translate_dyn(NodeId, Block, _, _), 1395 address_match(Address, Block), 1396 block_limit_address(Block, Limit) 1397 ) ; ( 1398 node_overlay(NodeId, _), 1399 Limit = [memory, [281474976710656]] % Default limit 1400 )). 1401 1402test_one_block_upper_limit :- 1403 assert(node_translate_dyn( 1404 ["In"], [memory, [block{base:1000,limit:2000}]], 1405 ["Out1"], [memory, [block{base:0,limit:1000}]])), 1406 one_block_upper_limit(name{node_id:["In"],address:[memory, [1400]]}, Limit), 1407 writeln(Limit), 1408 1409 assert(node_block_meta(["In1"], 21, ["Out1"])), 1410 one_block_upper_limit(name{node_id:["In1"],address:[memory, [1400]]}, Limit2), 1411 writeln(Limit2). 1412 1413% Internal function for region route 1414 1415route_step_new(S, SrcRegions, NextRegions, Route) :- 1416 (decode_step_regions(S, SrcRegions, NextRegions), Route=[]) ; 1417 decode_step_regions_conf(S, SrcRegions, NextRegions, Route). 1418 1419route_new(S, SrcRegions, DstRegions, Route) :- 1420 SrcRegion = region{node_id: SrcNodeId, blocks: SrcBlocks}, 1421 DstRegion = region{node_id: DstNodeId, blocks: DstBlocks}, 1422 route_step_new(S, SrcRegions, NextRegions, R1), 1423 (accept_or_hole_regions(S, NextRegions) -> ( 1424 DstRegions = NextRegions, 1425 Route = R1 1426 ) ; ( 1427 route_new(S, NextRegions, DstRegions, R2), 1428 union(R1, R2, Route) 1429 )). 1430 1431:- export test_route_new/0. 1432test_route_new :- 1433 Upper is 512 * 1024 * 1024, 1434 Limit2M is 2^21 - 1, 1435 S = [ 1436 mapping( 1437 region{node_id: ["IN"], blocks: [memory, block{base:0, limit:Upper}]}, 1438 name{node_id: ["MMU"], address: [memory, 0]}), 1439 block_meta(["MMU"], 21, ["RAM"]), 1440 accept(region{node_id: ["RAM"], blocks: [memory, block{base:0, limit: Upper}]}) 1441 ], 1442 state_valid(S), 1443 1444 route_new(S, 1445 [region{node_id:["IN"], blocks: [memory, block{base:0, limit: Limit2M}]}], 1446 OutRegions, Route), 1447 OutRegions = [region{node_id:["RAM"], blocks: [memory, block{base:0, limit: Limit2M}]}], 1448 Route = [block_conf(["MMU"], 0, 0)]. 1449 1450 1451 1452test_route(Route) :- 1453 init, add_pci, add_process, 1454 MMU_IN_ID = ["IN", "MMU0", "PROC0"], 1455 MMU_OUT_ID = ["OUT", "MMU0", "PROC0"], 1456 DRAM_ID = ["DRAM"], 1457 retract(node_translate_dyn(MMU_IN_ID,_,_,_)), % Make sure there is no route 1458 assert(node_block_meta(MMU_IN_ID, 21, MMU_OUT_ID)), 1459 alloc_range(DRAM_ID, [memory, [1024]], FreeDRAM), 1460 SrcName=name{node_id: MMU_IN_ID, address: [memory, [0]]}, 1461 DstName=name{node_id: DRAM_ID, address: FreeDRAM}, 1462 writeln(("Routing from", SrcName, " to ", DstName)), 1463 route(SrcName, DstName, Route), 1464 term_variables(Route, RouteVars), 1465 labeling(RouteVars), 1466 writeln(("Calculated", Route)). 1467 1468test_route2 :- 1469 init, add_pci, add_process, 1470 MMU_IN_ID = ["IN", "MMU0", "PROC0"], 1471 MMU_OUT_ID = ["OUT", "MMU0", "PROC0"], 1472 DRAM_ID = ["DRAM"], 1473 retract(node_translate_dyn(MMU_IN_ID,_,_,_)), % Make sure there is no route 1474 assert(node_block_meta(MMU_IN_ID, 21, MMU_OUT_ID)), 1475 alloc_range(DRAM_ID, [memory, [1024]], FreeDRAM), 1476 SrcName1=name{node_id: MMU_IN_ID, address: [memory, [0]]}, 1477 DstName1=name{node_id: DRAM_ID, address: FreeDRAM}, 1478 writeln(("Routing from", SrcName1, " to ", DstName1)), 1479 route_and_install(SrcName1, DstName1, Route1), 1480 writeln(("Calculated (1)", Route1)), 1481 SrcName2=name{node_id: MMU_IN_ID, address: [memory, [0]]}, 1482 DstName2=name{node_id: DRAM_ID, address: FreeDRAM}, 1483 writeln(("Routing from", SrcName2, " to ", DstName2)), 1484 route_and_install(SrcName2, DstName2, Route2), 1485 writeln(("Calculated (2) ", Route2)). 1486 1487 1488test_route_region_small :- 1489 assert(node_block_meta(["IN"], 21, ["OUT"])), 1490 assert(node_accept(["OUT"], [memory, [block{base:0, limit:100000}]])), 1491 route( 1492 region{node_id:["IN"], blocks:[memory,block{base:0, limit:1000}]}, 1493 region{node_id:["OUT"], blocks:[memory,block{base: 0, limit: 1000}]}, 1494 Route), 1495 term_variables(Route, RouteVars), 1496 labeling(RouteVars), 1497 1498 % check if it worked 1499 member((["IN"], 0, 0), Route), 1500 writeln(("Calculated", Route)). 1501 1502test_route_region_two :- 1503 Limit = 4194302, % 0x1fffff * 2 1504 assert(node_block_meta(["IN"], 21, ["OUT"])), 1505 assert(node_accept(["OUT"], [memory, [block{base:0, limit:4194303}]])), 1506 route( 1507 region{node_id:["IN"], blocks:[memory, block{base:0, limit:Limit}]}, 1508 region{node_id:["OUT"], blocks:[memory, block{base: 0, limit: Limit}]}, 1509 Route), 1510 term_variables(Route, RouteVars), 1511 labeling(RouteVars), 1512 1513 member((["IN"], 0, 0), Route), 1514 member((["IN"], 1, 1), Route), 1515 writeln(("Calculated", Route)). 1516 1517 1518test_route_all :- 1519 test_route_region_small, 1520 writeln("region small: passed"), 1521 test_route_region_two, 1522 writeln("region two: passed"). 1523 1524 1525% It is possible, to remap SrcName to DstName using the block remapping? 1526can_translate(SrcName, DstName, (SrcNodeId, (VPN, PPN))) :- 1527 name{ node_id: SrcNodeId, address: [K, [ISrcAddr]] } = SrcName, 1528 name{ node_id: DstNodeId, address: [K, [IDstAddr]] } = DstName, 1529 node_block_meta(SrcNodeId, BlockSizeBits, DstNodeId), 1530 split_vaddr(ISrcAddr, BlockSizeBits, [VPN, Offset]), 1531 split_vaddr(IDstAddr, BlockSizeBits, [PPN, Offset]), 1532 not(node_block_conf(SrcNodeId, VPN, _)). % No mapping with this VPN 1533 1534:- export install_route/1. 1535install_route([]). 1536 1537install_route([null | Ri]) :- 1538 install_route(Ri). 1539 1540install_route([(NodeId, VPN, PPN) | Ri]) :- 1541 assert(node_block_conf(NodeId, VPN, PPN)), 1542 install_route(Ri). 1543 1544 1545 1546%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1547%%%% X86 Page table configurable nodes 1548%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1549 1550% node_pt stores the root page table for per node 1551:- dynamic node_pt/3. % NodeId, RootPt, OutNodeId 1552:- dynamic pt/3. % PtIndex, Offset, NextPtIndex 1553:- export pt/3. 1554 1555split_vpn(VPN, Parts) :- 1556 assert_word(VPNW, 27), % 3 x 9 = 27 1557 word_to_num(VPNW, VPN), 1558 subword(VPNW, L1W, 1 .. 9), 1559 word_to_num(L1W, L1), 1560 subword(VPNW, L2W, 10 .. 18), 1561 word_to_num(L2W, L2), 1562 subword(VPNW, L3W, 19 .. 27), 1563 word_to_num(L3W, L3), 1564 Parts = [L3,L2,L1]. 1565 1566split_vaddr(VA, BlockSizeBits, [VPN, Offset]) :- 1567 assert_word(VAW, 48), 1568 word_to_num(VAW, VA), 1569 subword(VAW, OffsetW, 1 .. BlockSizeBits), 1570 word_to_num(OffsetW, Offset), 1571 VPNWStart is BlockSizeBits + 1, 1572 subword(VAW, VPNW, VPNWStart .. 48), 1573 word_to_num(VPNW, VPN). 1574 1575test_split_vpn :- 1576 VA = 16'40201, % hex(1 | 1<<9 | 1<<18) 1577 split_vpn(VA, [1,1,1]). 1578 1579 1580%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1581%%%% Tests 1582%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 1583 1584run_test(Test) :- 1585 ( 1586 call(Test), 1587 printf("Test %p succeeds!\n", Test) 1588 ) ; ( 1589 printf("!!! Test %p failed !!!\n", Test) 1590 ). 1591 1592:- export run_all_tests/0. 1593run_all_tests :- 1594 run_test(test_alignment), 1595 run_test(test_scan_points), 1596 run_test(test_max_not_translated_pt), 1597 run_test(test_translate), 1598 run_test(test_accept_name), 1599 run_test(test_accept_region), 1600 run_test(test_decode_step_name), 1601 run_test(test_decode_step_name2), 1602 run_test(test_decode_step_name3), 1603 run_test(test_decode_step_region1), 1604 run_test(test_decode_step_region2), 1605 run_test(test_decode_step_region3), 1606 run_test(test_resolve_name), 1607 run_test(test_resolve_name2), 1608 run_test(test_decode_step_region_conf_one), 1609 run_test(test_route_new), 1610 run_test(test_split_vpn), 1611 run_test(test_alloc_range), 1612 run_test(test_region_region_intersection). 1613