DIRECTORY
BasicTime USING [MicrosecondsToPulses, Pulses],
Booting USING [RegisterProcs, RollbackProc, switches],
CommBuffer USING [Encapsulation],
CommDriver USING [BufferObject, GetNetworkChain, Network],
Endian USING [CardFromF, FFromCard, FWORD],
Process USING [Detach, MsecToTicks, Pause, priorityNormal, SecondsToTicks, SetPriority, Ticks],
Pup USING [Address, allHosts, allNets, Host, Net, nullAddress, nullHost, nullSocket, Socket],
PupBuffer USING [Buffer, BufferObject, maxRoutingEntrys, RoutingInfoResponse],
PupHop USING [Hop, maxHop, Milliseconds, RoutingTableEntry, unreachable],
PupInternal USING [],
PupSocket USING [AllocBuffer, Broadcast, CreateServer, Destroy, FreeBuffer, Get, GetUserSize, Socket, Put, ReturnToSender, SetNoErrors, SetRemoteAddress, SetUserBytes, SetUserSize, waitForever],
PupWKS USING [gatewayInfo];

PupRouterImpl: CEDAR MONITOR
IMPORTS BasicTime, Booting, CommDriver, Endian, Process, PupSocket
EXPORTS PupHop, PupInternal = {

BYTE: TYPE = [0..100H);

Buffer: TYPE = PupBuffer.Buffer;
Hop: TYPE = PupHop.Hop;
Milliseconds: TYPE = PupHop.Milliseconds;
Network: TYPE = CommDriver.Network;
Pulses: TYPE = BasicTime.Pulses;

maxHop: Hop = PupHop.maxHop;
unreachable: Hop = PupHop.unreachable;

routingTable: RoutingTable _ NEW[RoutingTableArray _ ALL[NIL] ];
RoutingTable: TYPE = REF RoutingTableArray;
RoutingTableArray: TYPE = ARRAY BYTE OF RoutingSlot; -- NIL => no route
RoutingSlot: TYPE = REF RoutingInfo;
RoutingInfo: TYPE = RECORD [
hop: Hop _ unreachable, -- 0 => directly connected
network: Network _ NIL,
immediate: Pup.Host _ Pup.nullHost,
time: CARDINAL _ 0 ];

Route: PUBLIC PROC [him: Pup.Address] RETURNS [network: Network, immediate: Pup.Host] = {
routing: RoutingSlot _ routingTable[him.net];
IF routing = NIL THEN RETURN[NIL, Pup.nullHost];
IF routing.network = NIL THEN RETURN[NIL, Pup.nullHost];
IF routing.hop = 0 THEN RETURN[routing.network, him.host];
RETURN[routing.network, routing.immediate];
};

socket: PupSocket.Socket;
RoutingSlurper: PROC = {
Process.SetPriority[Process.priorityNormal];
DO
b: Buffer _ PupSocket.Get[socket];
SELECT b.type FROM
gatewayRequest => ProcessGatewayRequest[b, TRUE];
gatewayInfo => [] _ ProcessGatewayInfo[b];
ENDCASE =>  NULL;
PupSocket.FreeBuffer[b];
ENDLOOP;
};

routingTableChanges: LONG CARDINAL _ 0;
ProcessGatewayInfo: PUBLIC PROC [b: Buffer] RETURNS [changed: BOOL _ FALSE] = {
new: RoutingInfo;
entries: NAT = PupSocket.GetUserSize[b]/SIZE[PupBuffer.RoutingInfoResponse];
new.network _ NARROW[b.ovh.network];
new.immediate _ b.source.host;
IF new.immediate = new.network.pup.host THEN RETURN;
IF entries > PupBuffer.maxRoutingEntrys THEN RETURN;
IF new.network.pup.net = 0 THEN {
net: Pup.Net _ b.source.net;
new.network.pup.net _ b.source.net;
IF routingTable[0] = NIL OR new.network = CommDriver.GetNetworkChain[] THEN
routingTable[0] _ NEW[RoutingInfo _ [
hop: 0, network: new.network, immediate: [0], time: 0]];
routingTable[net] _ NEW[RoutingInfo _ [
hop: 0, network: new.network, immediate: [0], time: 0]]; };
FOR i: NAT IN [0..entries) DO
data: PupBuffer.RoutingInfoResponse _ b.routing[i];
net: Pup.Net _ data.net;
oldSlot: RoutingSlot _ routingTable[net];
old: RoutingInfo;
IF oldSlot # NIL THEN old _ oldSlot^ ELSE old _ [hop: maxHop, network: NIL];
IF old.hop = 0 THEN LOOP; -- directly connected
new.hop _ MIN[Hop.LAST, data.hop + 1];
IF new.network = old.network AND new.immediate = old.immediate THEN {
this: RoutingSlot _ routingTable[net]; -- Same path, update timer (and maybe hop)
IF new.hop > maxHop THEN {
new.hop _ maxHop + 1; -- dangling entry, don't rejuvenate timer
new.time _ old.time; }
ELSE new.time _ 0;
IF new.hop # old.hop THEN changed _ TRUE;
this.hop _ new.hop;
this.time _ new.time;
LOOP; };
IF old.hop > maxHop AND new.hop > maxHop THEN LOOP; -- couldn't get there, still can't
IF old.network = NIL -- couldn't get there, can now
OR old.time > 90 -- no recent response, try any alternate path
OR (new.hop = old.hop AND new.network.speed > old.network.speed) -- same hop, but faster
OR new.hop < old.hop THEN { -- better hop
IF new.hop > maxHop THEN {
new.hop _ maxHop + 1; -- dangling entry, don't rejuvenate timer
new.time _ old.time; }
ELSE new.time _ 0;
IF new.hop # old.hop THEN changed _ TRUE;
routingTable[net] _ NEW[RoutingInfo _ new];
routingTableChanges _ routingTableChanges.SUCC;
};
ENDLOOP;
};

ProcessGatewayRequest: PUBLIC PROC [b: Buffer, rejectBroadcasts: BOOL] = {
maxRoutingEntrys: NAT = PupBuffer.maxRoutingEntrys;
source, dest: Pup.Address;
id: Endian.FWORD;
index: [0..maxRoutingEntrys] _ 0;
broadcast: BOOL _ FALSE;
encap: CommBuffer.Encapsulation;
network: Network;
ReturnOrBroadcast: PROC [b: Buffer] = {
b.type _ gatewayInfo;
b.id _ id;
PupSocket.SetUserSize[b, index*SIZE[PupBuffer.RoutingInfoResponse]];
IF broadcast THEN PupSocket.Broadcast[socket, b]
ELSE {
b.ovh.encap _ encap;
b.ovh.network _ network;
b.source _ source;
b.dest _ dest;
PupSocket.ReturnToSender[b]; };
};
IF rejectBroadcasts AND b.dest.host = Pup.allHosts THEN RETURN;
IF b # NIL THEN {
source _ b.source;
dest _ b.dest;
id _ b.id;
encap _ b.ovh.encap;
network _ NARROW[b.ovh.network];
b _ NIL; } -- Don't use this buffer
ELSE {
broadcast _ TRUE;
id _ NextBroadcastID[]; };
FOR net: BYTE IN (BYTE.FIRST..BYTE.LAST] DO -- Skip net 0
this: RoutingSlot _ routingTable[net];
IF this = NIL THEN LOOP; -- no route
IF this.network = NIL THEN LOOP; -- no route
IF b = NIL THEN b _ PupSocket.AllocBuffer[socket];
b.routing[index] _ [
net: [net], viaNet: this.network.pup.net, viaHost: this.immediate, hop: this.hop];
IF this.hop = 0 THEN b.routing[index].viaHost _ this.network.pup.host;
index _ index + 1;
IF index = PupBuffer.maxRoutingEntrys THEN {
ReturnOrBroadcast[b];
b _ NIL;
index _ 0;
IF broadcast THEN id _ Succ[id]; };
ENDLOOP;
IF b # NIL THEN ReturnOrBroadcast[b];
};

nextBroadcastID: LONG CARDINAL _ 0;
NextBroadcastID: ENTRY PROC RETURNS [Endian.FWORD] = {
nextBroadcastID _ nextBroadcastID + 8;
RETURN[Endian.FFromCard[nextBroadcastID]];
};

Succ: PROC [x: Endian.FWORD] RETURNS [Endian.FWORD] = {
RETURN[Endian.FFromCard[Endian.CardFromF[x].SUCC]];
};

RoutingDemon: PROC = {
second: Process.Ticks = Process.SecondsToTicks[1];
Process.SetPriority[Process.priorityNormal];
DO
Process.Pause[second];
FOR net: BYTE IN BYTE DO
this: RoutingSlot _ routingTable[net];
IF this = NIL THEN LOOP; -- no route
IF this.hop = 0 THEN LOOP; -- directly connected
this.time _ this.time + 1; -- NOT ATOMIC
IF this.time > 180 THEN routingTable[net] _ NIL;
ENDLOOP;
ENDLOOP;
};

Rollback: Booting.RollbackProc = {
weeBit: Process.Ticks = Process.MsecToTicks[100];
FOR net: BYTE IN BYTE DO -- Smash all existing routes
this: RoutingSlot _ routingTable[net];
IF this = NIL OR this.hop = 0 THEN LOOP;
routingTable[net] _ NIL;
ENDLOOP;
FOR i: NAT IN [0..10) DO -- Ask gateways for up to date info
b: Buffer _ PupSocket.AllocBuffer[socket];
b.type _ gatewayRequest;
PupSocket.SetUserBytes[b, 0];
PupSocket.Put[socket, b];
Process.Pause[weeBit];
FOR net: BYTE IN BYTE DO
this: RoutingSlot _ routingTable[net];
IF this = NIL OR this.hop = 0 THEN LOOP;
Process.Pause[weeBit]; -- Give rest of info a chance to dribble in
RETURN;
ENDLOOP;
ENDLOOP;
};

InitializeRoutingInfo: PROC = {
socket _ PupSocket.CreateServer[local: PupWKS.gatewayInfo, getTimeout: 1000];
PupSocket.SetRemoteAddress[socket, [Pup.allNets, Pup.allHosts, PupWKS.gatewayInfo]];
FOR i: NAT IN [0..30) DO
b: Buffer _ PupSocket.AllocBuffer[socket];
this: RoutingSlot;
b.type _ gatewayRequest;
PupSocket.SetUserBytes[b, 0];
PupSocket.Put[socket, b];
DO
b: Buffer _ PupSocket.Get[socket];
IF b = NIL THEN EXIT;
SELECT b.type FROM
gatewayInfo => [] _ ProcessGatewayInfo[b];
ENDCASE =>  NULL;
PupSocket.FreeBuffer[b];
ENDLOOP;
FOR network: Network _ CommDriver.GetNetworkChain[], network.next UNTIL network = NIL DO
net: BYTE _ network.pup.net;
IF routingTable[0] = NIL THEN
routingTable[0] _ NEW[RoutingInfo _ [
hop: 0, network: network, immediate: [0], time: 0 ] ];
IF net # 0 THEN
routingTable[net] _ NEW[RoutingInfo _ [
hop: 0, network: network, immediate: [0], time: 0 ] ];
ENDLOOP;
this _ routingTable[0];
IF this # NIL AND this.network # NIL AND this.network.pup.net # 0 THEN EXIT;
ENDLOOP;
PupSocket.SetNoErrors[socket];
PupSocket.Destroy[socket];
socket _ PupSocket.CreateServer[local: PupWKS.gatewayInfo, getTimeout: PupSocket.waitForever];
PupSocket.SetRemoteAddress[socket, [Pup.allNets, Pup.allHosts, PupWKS.gatewayInfo]];
TRUSTED {
Process.Detach[FORK RoutingSlurper[]];
Process.Detach[FORK RoutingDemon[]]; };
};

GetHop: PUBLIC PROC [net: Pup.Net] RETURNS [Hop] = {
routing: RoutingSlot _ routingTable[net];
IF routing = NIL THEN RETURN[unreachable];
IF routing.network = NIL THEN RETURN[unreachable];
IF routing.hop > maxHop THEN RETURN[unreachable];
RETURN[routing.hop];
};

noRoute: PupHop.RoutingTableEntry = [
hop: unreachable, immediate: Pup.nullAddress, time: 0];
GetRouting: PUBLIC PROC [net: Pup.Net] RETURNS [rte: PupHop.RoutingTableEntry] = {
routing: RoutingSlot _ routingTable[net];
IF routing = NIL THEN RETURN[noRoute];
IF routing.network = NIL THEN RETURN[noRoute];
IF routing.hop = unreachable THEN RETURN[noRoute];
rte.hop _ routing.hop;
rte.immediate _ [routing.network.pup.net, routing.network.pup.host, Pup.nullSocket];
rte.time _ routing.time;
IF routing.hop = 0 THEN RETURN;
rte.immediate.host _ routing.immediate;
};

milliSecondsPerHop: Milliseconds = 500;
InitialTimeout: PUBLIC PROC [net: Pup.Net, base: Milliseconds] RETURNS [Milliseconds] = {
hop: PupHop.Hop = GetHop[net];
SELECT hop FROM
unreachable => RETURN[0];
IN [0..8] => RETURN[base +milliSecondsPerHop*hop];
ENDCASE => RETURN[base+milliSecondsPerHop*8];
};

pulsesPerHop: Pulses = BasicTime.MicrosecondsToPulses[milliSecondsPerHop*1000];
InitialTimeoutPulses: PUBLIC PROC [net: Pup.Net, base: Pulses] RETURNS [Pulses] = {
hop: PupHop.Hop = GetHop[net];
SELECT hop FROM
unreachable => RETURN[0];
IN [0..8] => RETURN[base +pulsesPerHop*hop];
ENDCASE => RETURN[base+pulsesPerHop*8];
};

Fast: PUBLIC PROC [net: Pup.Net] RETURNS [yes: BOOL] = {
routing: RoutingSlot _ routingTable[net];
IF routing = NIL THEN RETURN[FALSE];
IF routing.network = NIL THEN RETURN[FALSE];
SELECT routing.network.type FROM
ethernet => RETURN[TRUE];
ethernetOne => RETURN[TRUE];
ENDCASE => RETURN[FALSE];
};

Start: PROC = {
InitializeRoutingInfo[];
Booting.RegisterProcs[r: Rollback];
};

IF SIZE[CommDriver.BufferObject] < SIZE[PupBuffer.BufferObject] THEN ERROR;

IF ~Booting.switches[c] THEN Start[];

}.

PupRouterImpl.mesa
Copyright c 1986 by Xerox Corporation.  All rights reserved.
Hal Murray, October 31, 1986 3:03:13 pm PST
Russ Atkinson (RRA) April 25, 1986 5:07:14 pm PST

Outgoing Routing Table
Routing Table Updates
from self, so no need to process it
RRA: looks like a bogus packet, so discard it (defensive programming)
We don't know our network number on this device yet. If we are not a gateway, we have probably just learned the network number of the standard Ethernet device.
This is where we actually update the routing table. For all the details, see Taft's memo stored on: [MAXC]<Pup>GatewayInformation.bravo
This is a bit tricky.  We want to keep entrys with hop>maxHop until they timeout so that Gateways will do the right things about propagating changes, but we don't want to learn new paths to nowhere.
We like this new entry
As a debugging hack, answer routing requests that are specifically for us.
Don't answer broadcasts if we aren't a gateway.
We got some new info (at least one packet)
Wait long enough for DLion EthernetDriver to recapture head from HackPupHostNumber.
Start over to get our network number. This is a krock, but I don't have a better idea right now. It only helps when responding to gateway info requests.
Exported To PupHop

Initialization
Κ
Š˜
codeš
œ™Kšœ
Οm
œ1™<K™+K™1K™š
Οk	˜	Kšœ
žœ ˜/Kšœžœ)˜6Kšœžœ˜!Kšœžœ*˜:Kšœžœžœ˜+KšœžœR˜_KšœžœT˜]Kšœ
žœ?˜NKšœžœ=˜IKšœžœ˜Kšœ
žœ³
˜Β
Kšœžœ˜K˜——šΟn
œžœ
ž˜Kšžœ;˜BKšžœ˜K˜Kšžœžœ
˜K˜Kšœžœ˜ Kšœžœ˜Kšœžœ˜)Kšœ	žœ˜#Kšœžœ˜ K˜Kš
œ˜š
œ&˜&K˜——
head™Kšœžœžœ
žœ˜@Kšœžœžœ˜+Kš
œžœžœ
žœ
žœΟc˜GKšœ
žœžœ
˜$šœ
žœžœ˜Kšœ ˜2Kšœž˜Kš
œ#˜#Kšœžœ˜—K˜šŸœžœ
žœžœ,˜YKš
œ-˜-Kš
žœžœ
žœ
žœ
žœ˜0Kš
žœžœ
žœ
žœ
žœ˜8Kšžœžœ
žœ˜:Kšžœ%˜+Kš
œ˜K˜——™Kš
œ˜šŸœžœ˜Kš
œ,˜,š
ž˜Kš
œ"˜"šžœž˜Kšœ+žœ˜1Kš
œ*˜*Kšžœžœ
˜—Kš
œ˜Kšžœ
˜—K˜K˜—Kšœžœ
žœ˜'šŸœžœ
žœ
žœžœžœ˜OKš
œ˜Kšœ	žœžœ ˜LKšœžœ˜$K˜šžœ&žœ
žœ
˜4Kš
œ#™#—šžœ&žœ
žœ
˜4Kš
œE™E—šžœžœ˜!K˜Kš
œŸ
™Ÿ
Kš
œ#˜#šžœžœ
žœ,ž˜Kšœžœ˜%Kš
œ8˜8——šœžœ˜'Kš
œ;˜;——Kš
œ‡
™‡
šžœžœ
žœž˜Kš
œ3˜3K˜Kš
œ)˜)Kš
œ˜Kš
žœžœ
žœžœžœ˜LKšžœ
žœ
žœ ˜/Kš
œΖ
™Ζ
Kšœ
žœžœ˜&šžœžœžœ˜EKšœ' *˜Qšžœžœ˜Kšœ )˜?Kš
œ˜—Kšžœ˜Kšžœžœžœ
˜)Kš
œ˜K˜Kšžœ˜—Kš	žœžœžœ
žœ "˜Všžœžœ
 žœ .žœžœ( žœžœ 
˜υ
Kš
œ™šžœžœ˜Kšœ )˜?Kš
œ˜—Kšžœ˜Kšžœžœžœ
˜)Kšœžœ˜+Kšœ*žœ
˜/Kš
œ˜—Kšžœ
˜—K˜K˜—šŸœžœ
žœžœ˜JK™JKšœžœ˜3K˜Kšœžœ
˜Kš
œ!˜!Kšœžœžœ
˜Kš
œ ˜ K˜šŸœžœ˜'Kš
œ˜Kš
œ
˜
Kšœžœ!˜DKšžœžœ˜0š
ž˜K˜K˜K˜K˜K˜—K˜—šžœžœžœ
žœ
˜?Kš
œ/™/—šžœžœ
žœ˜K˜K˜Kš
œ
˜
Kš
œ˜Kšœ
žœ˜ Kšœžœ ˜#—šžœ˜Kšœžœ
˜Kš
œ˜—šžœžœ
žœžœ
žœžœ
žœžœ
 
˜9Kš
œ&˜&Kš	žœžœ
žœ
žœ ˜$Kš	žœžœ
žœ
žœ ˜,Kšžœžœ
žœ#˜2š
œ˜Kš
œR˜R—Kšžœžœ2˜FK˜šžœ$žœ˜,Kš
œ˜Kšœžœ
˜K˜
Kšžœžœ˜#—Kšžœ
˜—Kšžœžœ
žœ˜%K˜K˜—Kšœžœ
žœ˜#š
Ÿœžœ
žœ
žœ	žœ˜6Kš
œ&˜&Kšžœ$˜*K˜K˜—š
Ÿœžœžœžœ	žœ˜7Kšžœ&žœ˜3K˜K˜—šŸœžœ˜K˜2Kš
œ,˜,š
ž˜K˜š	žœžœ
žœ
žœ
ž˜Kš
œ&˜&Kš	žœžœ
žœ
žœ ˜$Kšžœžœ
žœ ˜0Kšœ 
˜(Kšžœžœžœ
˜0Kšžœ
˜—Kšžœ
˜—K˜K˜—•StartOfExpansion -- [clientData: REF ANY]šΟbœ˜"Kš
œ1˜1šžœžœ
žœ
žœ
žœ
 ˜5Kš
œ&˜&Kš
žœžœ
žœžœ
žœ
˜(Kšœžœ
˜Kšžœ
˜—š	žœžœ
žœ	žœ
 #˜<Kš
œ*˜*K˜K˜K˜Kš
œ˜š	žœžœ
žœ
žœ
ž˜Kš
œ&˜&Kš
žœžœ
žœžœ
žœ
˜(Kš
œ*™*Kšœ +˜BKšžœ
˜Kšžœ
˜—Kšžœ
˜—K˜K˜—šŸœžœ˜Kš
œM˜MKš
œT˜Tšžœžœ
žœ	ž˜Kš
œS™SKš
œ*˜*Kš
œ˜K˜K˜K˜š
ž˜Kš
œ"˜"Kšžœžœ
žœ
žœ
˜šžœž˜Kš
œ*˜*Kšžœžœ
˜—Kš
œ˜Kšžœ
˜—šžœ?žœžœ
ž˜XKšœžœ˜šžœžœ
ž˜šœžœ˜%Kš
œ6˜6——šžœ	ž˜šœžœ˜'Kš
œ6˜6——Kšžœ
˜—Kš
œ˜Kšžœžœ
žœžœ
žœžœ
žœ
˜LKšžœ
˜—Kš
œ˜
™˜
Kš
œ˜Kš
œ˜Kš
œ^˜^Kš
œT˜Tšžœ˜	Kšœžœ˜&Kšœžœ˜'—K˜K˜——š
œ™šŸœžœ
žœžœ
˜4Kš
œ)˜)Kšžœžœ
žœ
žœ˜*Kšžœžœ
žœ
žœ˜2Kšžœžœ
žœ˜1Kšžœ˜K˜K˜—š
œ%˜%Kš
œ7˜7—šŸ
œžœ
žœžœ$˜RKš
œ)˜)Kšžœžœ
žœ
žœ
˜&Kšžœžœ
žœ
žœ
˜.Kšžœžœ
žœ
˜2Kš
œ˜Kš
œT˜TKš
œ˜Kšžœžœ
žœ
˜Kš
œ'˜'K˜K˜—Kš
œ'˜'šŸœžœ
žœ$žœ˜YIcode2š
œ˜šžœž˜Mšœžœ˜Mšžœžœ˜2Mšžœžœ˜-—K˜K˜—Kš
œO˜OšŸœžœ
žœžœ
˜SMš
œ˜šžœž˜Mšœžœ˜Mšžœžœ˜,Mšžœžœ˜'—K˜K˜—š
Ÿœžœ
žœžœžœ˜8Kš
œ)˜)Kš
žœžœ
žœ
žœ
žœ˜$Kš
žœžœ
žœ
žœ
žœ˜,šžœž˜ Kšœžœ
žœ˜Kšœžœ
žœ˜Kšžœžœ
žœ˜—K˜K˜K™——™šŸœžœ˜K˜Kš
œ#˜#K˜K˜—šžœ
žœžœž
œ
˜KK˜—šžœžœ	˜%K˜——š
œ˜K˜——…—(δ;v