// PupRoute.bcpl -- Module implementing the Pup Routing Table
// Copyright Xerox Corporation 1979, 1982

// Last modified September 24, 1982  4:13 PM by Taft

get "Pup0.decl"
get "Pup1.decl"
get "PupRoute.decl"

// outgoing procedures
GatewayListener; LocateNet
RTLookup; RTEnumerate; RTInsert; RTDelete

// incoming procedures
Forwarder; ForwarderCtx
SetTimer; TimerHasExpired; Dismiss; Min
ReleasePBI; GetPBI; CompletePup
Allocate; Zero; SetBlock; MoveBlock; Enqueue; Dequeue
HLookup; HEnumerate; HInsert; HDelete

// outgoing statics
pupRT; gatewayListenerSoc

// incoming statics
ndbQ; pupZone

static [ pupRT; gatewayListenerSoc ]

// This module plugs into GateForward.bcpl - the Gateway Forwarder,
//  or into PupDummyGate, if this isn't a gateway.

// Routing table maintenance:
// The routing table is treated as a cache of recently-used routing
// information.  It is implemented as a fixed-length queue of RTQIs
// (routing table queue items), each of which contains an RTE.
// Lookups are implemented simply by searching the queue.  Each successful
// lookup causes the associated RTE to be promoted to the front of the queue,
// thereby speeding subsequent lookups of the same net. A new entry is
// inserted by taking an RTE off the end of the queue and re-using it.

// The GatewayListener maintains all existing RTEs, and adds new ones
// only if free RTEs happen to exist.  When a higher-level caller
// (e.g., RoutePup) requires a route to a net for which there is no RTE,
// it calls LocateNet, which creates a new RTE and initiates a routing probe.

// Conventions:
// A free RTE is represented by net = rtFreeEntry.
// All free RTEs are maintained at the end of the queue.
// RTEs for directly-connected networks are never deleted.
// An RTE that has been created in response to LocateNet but not yet
// filled in has hops = maxHops+1 and ndb = 0.
let LocateNet(net) = valof
// Externally-called procedure that attempts to locate a route to a net.
// If a route is known, returns the RTE for it; if not, initiates activity
// to attempt to locate the desired route and returns zero.
let rte = HLookup(pupRT, net)
if rte ne 0 & rte>>RTE.hops le maxHops then resultis rte
if rte eq 0 then
   // No RTE exists.  Insert an RTE for net so as to get it into the cache
   rte = HInsert(pupRT, net)
   rte>>RTE.hops = maxHops+1
   SetTimer(lv rte>>RTE.timer, 3000)  // Delete in 30 sec if no route found

// initiate a probe for routing information.
pupRT>>RT.probeCount = 10  // try 10 times
SetTimer(lv pupRT>>RT.probeTimer, 0)
resultis 0

and RTLookup(rt, net, dontPromote; numargs na) = valof
// Returns pointer to RTE for net, or zero if not found.
// Moves the matching RTE to the head of the queue unless dontPromote.
// See whether head item is the one we want; if so, return it quickly.
let rtqi = rt>>RT.head
if net eq rtqi>>RTQI.rte.net resultis lv rtqi>>RTQI.rte

// Search queue for matching rte
   [ // repeat
   let nrtqi = rtqi>>RTQI.next
   if nrtqi eq 0 resultis 0  // not found
   if net eq nrtqi>>RTQI.rte.net then
      [ // found matching RTE (nrtqi)
      unless na ge 3 & dontPromote do
         [ // promote it to the head of the queue
         rtqi>>RTQI.next = nrtqi>>RTQI.next
         if rtqi>>RTQI.next eq 0 then rt>>RT.tail = rtqi
         nrtqi>>RTQI.next = rt>>RT.head
         rt>>RT.head = nrtqi
      resultis lv nrtqi>>RTQI.rte
   rtqi = nrtqi
   ] repeat
and RTEnumerate(rt, Proc, arg) be
// Calls Proc(rte, arg) for every valid entry in rt
let rtqi = rt>>RT.head
   if rtqi>>RTQI.rte.net ne rtFreeEntry then Proc(lv rtqi>>RTQI.rte, arg)
   rtqi = rtqi>>RTQI.next
   ] repeatwhile rtqi ne 0

and RTInsert(rt, net) = valof
// Returns pointer to an RTE where net can be inserted.
// net is in the net field and the rest of the RTE is zeroed.
let rte = HLookup(rt, net)
if rte eq 0 then
   // Not found, grab the tail item and put it at the head.
   // n.b. Do not allow RTEs for directly-connected networks to be deleted.
   rte = HLookup(rt, rt>>RT.tail>>RTQI.rte.net)
   ] repeatwhile rte>>RTE.net ne rtFreeEntry & rte>>RTE.hops eq 0
Zero(rte, lenRTE)
rte>>RTE.net = net
resultis rte

and RTDelete(rt, net) be
let rte = HLookup(rt, net)
if rte ne 0 then
   // Mark RTE deleted and put it at the end of the queue.
   // n.b. we know it is at the head now, because RTLookup put it there.
   rte>>RTE.net = rtFreeEntry
   Enqueue(lv rt>>RT.head, Dequeue(lv rt>>RT.head))
and GatewayListener() be
// This process listens for gratuitous routing table broadcasts from
//  gateways and updates our local routing table.
// If we are a gateway, also listens for gateway info requests
//  and responds appropriately.
// Purges routing table entries that haven't been updated recently.
// Generates gateway routing info probes if required.
let updateTimer = nil; SetTimer(lv updateTimer, 0)
   if TimerHasExpired(lv updateTimer) then
      //every 15 seconds age the RT entries
      RTEnumerate(pupRT, AgeRTE, pupRT)
      SetTimer(lv updateTimer, 1500)

   while gatewayListenerSoc>>PupSoc.iQ.head ne 0 do
      let pbi = Dequeue(lv gatewayListenerSoc>>PupSoc.iQ)
      test pbi>>PBI.pup.type eq ptRouteReply
         ifso test pbi>>PBI.pup.sPort.host ne pbi>>PBI.ndb>>NDB.localHost
            ifso ProcessRouteInfoReply(pbi)  //ignore our own bcsts
            ifnot ReleasePBI(pbi)
         ifnot Forwarder(pbi)  // maybe the gateway knows how to handle it 

   if pupRT>>RT.probeCount gr 0 &
    TimerHasExpired(lv pupRT>>RT.probeTimer) then
      //broadcast a routing info request on each directly-connected network
      let pbi = GetPBI(gatewayListenerSoc, true)
      if pbi ne 0 then
         pbi>>PBI.allNets = true
         CompletePup(pbi, ptRouteRequest, pupOvBytes)
         SetTimer(lv pupRT>>RT.probeTimer, 200) // 2 seconds
         pupRT>>RT.probeCount = pupRT>>RT.probeCount-1

   // If this is a gateway, let it forward some packets.
   // This is a call to Dismiss(1) if no forwarder is present.
   ] repeat

and AgeRTE(rte, rt) be
if rte>>RTE.hops ne 0 & TimerHasExpired(lv rte>>RTE.timer) then
   test rte>>RTE.recent
      ifso  //first timeout, make entry eligible for replacement
         rte>>RTE.recent = false
         SetTimer(lv rte>>RTE.timer, rtTimeoutInterval)
      ifnot HDelete(rt, rte>>RTE.net)  //second timeout, purge entry
and ProcessRouteInfoReply(pbi) be
// Update local RT with stuff in ImAGateway pup.
// Note that the identity of the directly connected net has already been
// established in PupLevel1, if it wasn't previously known.  Here we update
// our rt as appropriate with each of the 4-byte info blocks in the Pup.
let net = pbi>>PBI.pup.dPort.net  //directly connected net
let host = pbi>>PBI.pup.sPort.host  //gateway host on net
if net ne 0 & pbi>>PBI.pup.sPort.socket↑1 eq 0 &  // Just being suspicious...
 pbi>>PBI.pup.sPort.socket↑2 eq psRouteInfo then
   pupRT>>RT.probeCount = 0
   for c = 1 to pbi>>PBI.pup.length-pupOvBytes by 4 do
      // Compute our hop count to target net via this gateway.
      let hops = Min(pbi>>PBI.pup.bytes↑(c+3), maxHops)+1

      // Look up target net in RT.
      net = pbi>>PBI.pup.bytes↑c
      let rte = HLookup(pupRT, net, true)
      test rte eq 0
            // Target net not in RT.
            // If target net is inaccessible, don't insert new RTE for it.
            // Otherwise, insert new RTE only if a free RTE is available.
            if hops gr maxHops loop
            if pupRT>>RT.tail>>RTQI.rte.net ne rtFreeEntry loop
            rte = HInsert(pupRT, net)  // Sets entire rte to zero
            // Target net already in RT.  If directly connected, do nothing.
            if rte>>RTE.hops eq 0 loop

      // Update rt entry with this info block if
      // (1) an rte didn't previously exist for this net, or
      // (2) the existing entry has timed out (recent = false), or
      // (3) the new gateway net/host is the same as in the rte, or
      // (4) the new route has fewer hops than the existing one.
      // Note that if (1) was true, a new rte will have been created (above),
      // with contents zeroed out, which will satisfy (2) here.
      if rte>>RTE.recent eq false %  // (2)
       pbi>>PBI.ndb eq rte>>RTE.ndb & host eq rte>>RTE.host %  // (3)
       hops ls rte>>RTE.hops then  // (4)
         // Note whether anything has really changed.
         unless hops eq rte>>RTE.hops do pupRT>>RT.changed = true

         // Insert route into rte.
         rte>>RTE.host = host  //via gateway host
         rte>>RTE.ndb = pbi>>PBI.ndb  //RT->ndb
         rte>>RTE.hops = hops

         // Reset rte timeout only if the target net is now accessible.
         // The idea is to cause permanently inaccessible nets eventually
         // to be purged.  Actually, in non-gateway hosts, we could purge
         // inaccessible nets immediately;  however, knowledge of a network's
         // inaccessibility must be remembered for a while by gateway hosts
         // and passed among them explicitly so that alternate routes will
         // be discovered quickly.
         if hops le maxHops then
            rte>>RTE.recent = true  //recently updated
            SetTimer(lv rte>>RTE.timer, rtTimeoutInterval)