
    <<PupRouterImpl.mesa>>
        <<Copyright © 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>>
        <<>>
        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];
        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;
            <<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];
        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;
                <<We got some new info (at least one packet)>>
                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
            <<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];
            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;
        <<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[];

    }.