[Cyan]<Cedar6.1>Pup>PupRouterImpl.mesa!4

PupRouterImpl.mesa

Hal Murray, October 31, 1986 3:03:13 pm PST

Russ Atkinson (RRA) April 25, 1986 5:07:14 pm PST

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;

Outgoing Routing Table

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];

};

Routing Table Updates

socket: PupSocket.Socket;

RoutingSlurper: PROC = {

Process.SetPriority[Process.priorityNormal];

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;

from self, so no need to process it

IF entries > PupBuffer.maxRoutingEntrys THEN RETURN;

RRA: looks like a bogus packet, so discard it (defensive programming)

IF new.network.pup.net = 0 THEN {

net: Pup.Net ← b.source.net;

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.

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]]; };

This is where we actually update the routing table. For all the details, see Taft's memo stored on: [MAXC]<Pup>GatewayInformation.bravo

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

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.

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

We like this new entry

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] = {

As a debugging hack, answer routing requests that are specifically for us.

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;

Don't answer broadcasts if we aren't a gateway.

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];

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;

};

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;

We got some new info (at least one packet)

Process.Pause[weeBit]; -- Give rest of info a chance to dribble in

RETURN;

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

Wait long enough for DLion EthernetDriver to recapture head from HackPupHostNumber.

b: Buffer ← PupSocket.AllocBuffer[socket];

this: RoutingSlot;

b.type ← gatewayRequest;

PupSocket.SetUserBytes[b, 0];

PupSocket.Put[socket, b];

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;

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.

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[]]; };

};

Exported To PupHop

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];

};

Initialization

Start: PROC = {

InitializeRoutingInfo[];

Booting.RegisterProcs[r: Rollback];

};

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

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