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