-- File: RoutingTableImpl.mesa - last edit:
-- AOF                  7-Jan-88 18:48:32
-- WIrish              26-Jan-87 11:38:03
-- SMA                 23-May-86  8:56:17
-- Copyright (C) 1984, 1985, 1986, 1987, 1988 by Xerox Corporation. All rights reserved. 
-- Function: The implementation module for the Pilot NS Router's routing table.

DIRECTORY
  Buffer,
  CommFlags USING [doDebug, doStats],
  CommPriorities USING [receiver],
  Driver USING [GetDeviceChain, Glitch, Device, PutOnGlobalDoneQueue],
  Environment USING [bytesPerWord, wordsPerPage],
  Inline USING [DBITSHIFT, BITAND, LongCOPY],
  NSConstants USING [routingInformationSocket],
  NSTypes USING [
    BufferBody, bytesPerIDPHeader, RoutingInfoTuple, RoutingInfoType,
    TransportControl, bytesPerRoutingHeader],
  Mopcodes USING [zEXCH],
  NSBuffer USING [
    AccessHandle, Body, Dequeue, Enqueue, GetBuffer, Buffer, QueueCleanup,
    QueueInitialize, QueueObject, ReturnBuffer],
  Process USING [
    Abort, Detach, EnableAborts, GetPriority, MsecToTicks, Priority,
    SetPriority, SetTimeout, Yield],
  Protocol1 USING [EncapsulateAndTransmit, GetContext],
  RoutingTable USING [Handle, FlushCacheProc, NetworkContext, Object],
  Router USING [FindMyHostID, infinity, NoTableEntryForNet, RoutersFunction],
  RouterInternal USING [
    BroadcastThisPacket, SendErrorPacket, XmitStatus],
  RouterOps USING [RouteDetails, DetailSequence, DetailList],
  Socket USING [
    Create, ChannelHandle, Delete, GetBufferPool, GetPacket, GetSendBuffer,
    SetPacketBytes, SetWaitTime, PutPacket, TimeOut],
  SocketInternal USING [ListenerProcType, CreateListen],
  Space USING [GetMapUnitAttributes, Interval, ScratchMap, Unmap, Usage],
  SpaceUsage USING [CommunicationUsage],
  Stats USING [StatIncr],
  SpecialSystem USING [HostNumber, NetworkNumber, SocketNumber],
  System USING [
    GetClockPulses, HostNumber, MicrosecondsToPulses, NetworkAddress,
    NetworkNumber, nullHostNumber, nullNetworkNumber, broadcastHostNumber,
    nullSocketNumber, nullNetworkAddress];

RoutingTableImpl: MONITOR
  IMPORTS
    NSBuffer, Driver, Inline, Process, Protocol1, Router,
    RouterInternal, Socket, SocketInternal, Space, Stats, System
  EXPORTS Buffer, RouterInternal, RouterOps, System =
  BEGIN

  --EXPORTed TYPEs
  Device: PUBLIC <<Buffer>> TYPE = Driver.Device;
  NetworkNumber: PUBLIC <<System>> TYPE = SpecialSystem.NetworkNumber;
  HostNumber: PUBLIC <<System>> TYPE = SpecialSystem.HostNumber;
  SocketNumber: PUBLIC <<System>> TYPE = SpecialSystem.SocketNumber;

  PutOnGlobalDoneQueue: PROC[b: NSBuffer.Buffer] =
    LOOPHOLE[Driver.PutOnGlobalDoneQueue];  --just to save n LOOPHOLEs
  
  TableBase: TYPE = LONG BASE POINTER;
  TableRelative: TYPE = TableBase RELATIVE ORDERED POINTER
    [0..LAST[CARDINAL]] TO TableElement;
  TableElement: TYPE = RECORD[
    net: NetworkNumber ← System.nullNetworkNumber,  --ultimate destination net
    delay: CARDINAL[0..256) ← FIRST[CARDINAL],  --measured in hops to remote net
    age: CARDINAL[0..256) ← youngster,  --age without new routing info
    lastAccess: LONG CARDINAL ← System.GetClockPulses[],  --when last used
    context: RoutingTable.NetworkContext ← NIL,  --access to driver
    route: HostNumber ← System.nullHostNumber,  --immediate host along the way
    rlink: TableRelative ← endLink];  --link to overflow element 
  
  Entry: TYPE = LONG POINTER TO TableElement;	--what's passed around inside

  table: RECORD[
    base: TableBase ← NIL,  --base of routing table
    nEntries: NATURAL ← 0,  --currently in the table
    fill: NATURAL ← 0,  --radius of table to maintain
    users: NATURAL ← 0,  --number of requests with non-zero fill requests
    maxLink: TableRelative ← nullLink,  --number overflow will hold
    cache: TableRelative ← cacheHint,  --emtpy slot hint
    me: TableElement ← []];  --primary net number

  endLink: TableRelative = LAST[TableRelative];
  nullLink: TableRelative = FIRST[TableRelative];
  defaultFirstPages: NATURAL = 2;  --starting off point
  defaultGrowPages: NATURAL = 8;  --how much we add each time
  firstTablePages: NATURAL ← defaultFirstPages;  --getting off the ground
  growTablePages: NATURAL ← defaultGrowPages;  --how much we add each time
  maxTableSize: NATURAL ← defaultFirstPages + (4 * defaultGrowPages);
  hashLog: NATURAL = 16;  --number of entries in basic table
  hashMask: NATURAL = hashLog - 1;  --used as bitand mask for hashing
  cacheHint: TableRelative = LOOPHOLE[hashLog * SIZE[TableElement]];
  tableUsage: Space.Usage = FIRST[SpaceUsage.CommunicationUsage] + 2;
  
  youngster: CARDINAL[0..256) = 0;  --age of fresh entries 
  longerAge: CARDINAL[0..256) = 3;  --age at which we accept longer routes 
  flushAge: CARDINAL[0..256) = 6;  --age at which we flush old entries 

  routerProcess: PROCESS;  -- does cache fault and sends buffer.

  mask: CARDINAL = 31;  -- for masking out the high eleven bits of the incoming
                        -- delay, as we (vanilla routing tables) don't use them.
  startEnum: NetworkNumber = System.nullNetworkNumber;
  endEnum, allNets: NetworkNumber = [177777B, 177777B];
  myHostID: HostNumber;                     -- host ID of this system element.
  tableLife: LONG CARDINAL ←
    System.MicrosecondsToPulses[90D6];  -- 90 sec, life in table w/o accesses.
  timeToCheck: LONG CARDINAL ←
    System.MicrosecondsToPulses[25D6];  -- 25 sec, scan interval through table
  faultDally: LONG CARDINAL ←
    System.MicrosecondsToPulses[25D5];  -- 2.5 sec, to gather cache faults
  initialTransportControl: NSTypes.TransportControl = [
    trace: FALSE, filler: 0, hopCount: 0];  -- for sending broadcasts.
  localHop: CARDINAL = 0;                   -- delay for attached network(s).
  myAccessHandle: NSBuffer.AccessHandle;    -- for obtaining buffers when sending
                                            -- via driver.
  cH: Socket.ChannelHandle;                 -- routing information socket handle.
  pleaseStop: BOOLEAN;                      -- switch to tell processes to stop.
  infoArrival: CONDITION;                   -- requested routing info arrived.
  requestedInfoQueue: NSBuffer.QueueObject; -- queue of directed responses.
  waitingDirectResp: CARDINAL;              -- do we want to keep direct resp's?
  clientFills: CARDINAL;                    -- number of non zero fills.
  routerCondition: CONDITION;  --buffer to find route for and send.
  outQueue: NSBuffer.QueueObject;  --send buffers that need routing information.
  -- Routing Table Object
  defaultRth: PUBLIC RoutingTable.Handle ← @rto;  --so router can find us
  rto: RoutingTable.Object ← [
    type: vanillaRouting, start: Start, stop: Stop,
    startEnumeration: startEnum, endEnumeration: endEnum,
    enumerate: Enumerate, fillTable: Fill,
    getDelay: GetDelay, transmit: Transmit,
    forward: Forward, findNetwork: FindLocalNetID,
    addNetwork: AddDriver, removeNetwork: RemoveDriver,
    flushCache: FlushCache, stateChanged: ChangedState];

  maxListLength: NATURAL ← 100;  --max length of table lists
  badEntry: NATURAL ← 0;  --for counting bogus entries added to table
  
  RoutingTableScrambled: ERROR = CODE; --mass confusion, etc
  DriverDidntNoteNet: ERROR = CODE;  --buffer came from busted driver
  NoBufferInQueue: ERROR = CODE;  --queue length > 0 but no buffers
  CacheFaultFailure: ERROR = CODE;  --supposed to spend 2.5 seconds faulting
  timeOfLastCheck: LONG CARDINAL ← System.GetClockPulses[];

  SanityCheck: <<DEBUGGING>> INTERNAL PROC[] = INLINE
    BEGIN
    SELECT TRUE FROM
      (table.base = NIL) => RETURN;  --not ready
      (Inline.BITAND[table.cache, 8000H] # 0) =>
        Driver.Glitch[RoutingTableScrambled];
      (Inline.BITAND[table.maxLink, 8000H] # 0) =>
        Driver.Glitch[RoutingTableScrambled];
      (table.cache > table.maxLink) =>
        Driver.Glitch[RoutingTableScrambled];
      ENDCASE;
    END;  --SanityCheck
  
  AddElement: INTERNAL PROC[net: NetworkNumber] RETURNS[entry: Entry] =
    BEGIN
    hash, link: TableRelative;
    IF CommFlags.doDebug AND (net.a # 0) THEN badEntry ← SUCC[badEntry];
    SELECT TRUE FROM
      (net = System.nullNetworkNumber) => RETURN[NIL];  --I ain't add'n that
      (net = table.me.net) => RETURN[@table.me];  --that one's special
      (table.base = NIL) => {Expand[]; RETURN[AddElement[net]]};
      (table.base[hash ← Hash[net.b]].net # System.nullNetworkNumber) =>
	BEGIN
	--start a serial search at table.cache looking for an empty slot
	FOR link ← table.cache, link + SIZE[TableElement]
	  WHILE link < table.maxLink DO
	  IF table.base[link].net = System.nullNetworkNumber THEN
	    BEGIN
	    table.cache ← link + SIZE[TableElement];  --update cache
	    (entry ← @table.base[link])↑ ← [  --set net and copy old link
	      net: net, rlink: table.base[hash].rlink, age: youngster];
	    table.base[hash].rlink ← link;  --link base entry to new
	    EXIT;
	    END;
	  REPEAT FINISHED => {Expand[]; RETURN[AddElement[net]]};
	  ENDLOOP;
	END;
      ENDCASE => (entry ← @table.base[hash])↑ ← [net: net];  --primary slot
    table.nEntries ← SUCC[table.nEntries];  --and count the entry
    IF CommFlags.doDebug THEN SanityCheck[];
    END;  --AddElement

 AddDriver: <<PUBLIC>> PROC [context: RoutingTable.NetworkContext] =
    BEGIN
    -- If the net number of the new attached network is known, calls
    -- AddDriverLocked to tell the routing table about it, else tries
    -- to find out net number by probing an INR.
    IF context.netNumber = System.nullNetworkNumber THEN ProbeINRs[]
    ELSE AddDriverLocked[context];
    END;  --AddDriver

  AddDriverInternal: INTERNAL PROC [context: RoutingTable.NetworkContext] =
    BEGIN
    <<
    Tells the routing table about a new attached network.  The driver
    must know the network number at this point.  Called by 
    ExamineResponse and Locked, both of which hold the monitor.
    >>
    entry: Entry;
    SELECT TRUE FROM
      (~context.network.alive) => RETURN;
      ((entry ← FindElement[context.netNumber, FALSE]) # NIL) => RETURN;
      ((entry ← AddElement[context.netNumber]) = NIL) => RETURN;  --null net
      ENDCASE;
    entry.context ← context;  --finish loading the entry
    IF CommFlags.doDebug AND (entry.net = System.nullNetworkNumber) THEN
      Driver.Glitch[RoutingTableScrambled];
   END;  --AddDriverInternal
   
  AddDriverLocked: ENTRY PROC [context: RoutingTable.NetworkContext] = INLINE
    {AddDriverInternal[context]};
  			      
      
  CheckRoutingTableEntries: INTERNAL PROC[] =
    BEGIN
    <<
    Scan the routing table aging entries as we go.
    Delete any entries that are so old that they should be flushed.
    Start the scan at each of the hashLog base entries, chasing the links
    until we hit an endLink.  If deleting causes the table to collapse, take
    an early return.
    >>
    prev, this, next: TableRelative;
    hashLink: TableRelative ← nullLink;  --equivalent to base slot==0;
    IF table.base = NIL THEN RETURN;  --doesn't take long to figure that out
    THROUGH[0..hashLog) DO
      prev ← endLink;  --just a known value to compare with
      IF CommFlags.doDebug THEN SanityCheck[];
      FOR this ← hashLink, next UNTIL this = endLink DO
	entry: Entry ← @table.base[this]; --for faster access
	IF entry.net = System.nullNetworkNumber THEN EXIT;  --empty|broken chain
	next ← entry.rlink;  --'next' is after entry to empty
	SELECT TRUE FROM
	  (entry.context.network.device > ethernetOne) => prev ← this;
	  ((entry.age ← entry.age.SUCC) >= flushAge),  --the entry is old
	  ((entry.delay > table.fill) AND  --not filling this full
	    ((System.GetClockPulses[] - entry.lastAccess) > tableLife)) =>
	    BEGIN
	    IF (table.nEntries ← PRED[table.nEntries]) = 0 THEN
	      BEGIN
	      table.base ← Space.Unmap[table.base];
	      table.maxLink ← nullLink; table.cache ← cacheHint;
	      RETURN;  --that's about the end of it
	      END;
	    SELECT TRUE FROM
	      (prev # endLink) =>  --in the middle or at the end
		BEGIN
		table.base[prev].rlink ← next;  --'prev' ← 'next'; empty 'this'
		END;
	      (next # endLink) =>  --at the beginning and not a lone entry
		BEGIN
		entry↑ ← table.base[next];  --copy 'next' on top of 'this'
		this ← next;  --set up so that 'this'='next' gets emptied
		next ← hashLink;  --back to beginning of the list
		END;
	      ENDCASE;  --the one and only entry, and it's from the base
	    table.base[this] ← [];  --empty 'this' entry
	    table.cache ← MAX[cacheHint, MIN[table.cache, this]];  --adjust cache
	    END;
	  ENDCASE => prev ← this;  --chase the chain
	ENDLOOP;
      hashLink ← hashLink + SIZE[TableElement];  --go to next bucket of base
      Process.Yield[];  --share the candy a little bit
      ENDLOOP;
    IF CommFlags.doDebug THEN SanityCheck[];
    END;  -- of CheckRoutingTableEntries
    
    
  ChangedState: PROC[context: RoutingTable.NetworkContext] =
    BEGIN
    RemoveDriver[context];
    AddDriver[context];
    END;  --ChangedState

  CleanUpRoutingTable: ENTRY PROC = INLINE
    {IF table.base # NIL THEN [] ← Space.Unmap[table.base]; table ← []};

  Enumerate: <<PUBLIC>> ENTRY PROCEDURE[
    previous: System.NetworkNumber, delay: CARDINAL]
    RETURNS [net: System.NetworkNumber ← endEnum] =
    BEGIN
    LongSwap: PROC[net: System.NetworkNumber] RETURNS[LONG CARDINAL] =
      MACHINE CODE {Mopcodes.zEXCH};
    NetAgtNetB: PROC [a, b: System.NetworkNumber] RETURNS [BOOLEAN] = INLINE
      {RETURN[LongSwap[a] > LongSwap[b]]};
    TestThisNet: PROC[] RETURNS [] = 
      BEGIN
      SELECT TRUE FROM
	(tuple.objectNetID = System.nullNetworkNumber) => NULL;
	(tuple.interrouterDelay = delay) 
	  AND NetAgtNetB[tuple.objectNetID, previous]
	  AND ~NetAgtNetB[tuple.objectNetID, net] => net ← tuple.objectNetID;
	ENDCASE;
      END;  --TestThisNet

    <<
    The first entry processed is always the local net.  This makes the
    loading of 'tuple' and seem strange.  Have faith.
    >>
    hashLink: TableRelative ← nullLink;  --equivalent to base slot==0;
    tuple: NSTypes.RoutingInfoTuple ← [table.me.net, table.me.delay];
    TestThisNet[];  --try the local net first
    THROUGH[0..hashLog) WHILE (table.base # NIL) DO
      rlink: RoutingTableImpl.TableRelative;
      FOR rlink ← hashLink, rlink ← table.base[rlink].rlink
        UNTIL rlink = endLink DO
        tuple ← [table.base[rlink].net, table.base[rlink].delay];
	TestThisNet[];  --is this one any better?
	ENDLOOP;
      hashLink ← hashLink + SIZE[TableElement];
      ENDLOOP; 
    END;  --Enumerate

  Expand: INTERNAL PROC[] =
    BEGIN
    interval: Space.Interval;
    stretch, original: CARDINAL;

    IF CommFlags.doDebug THEN SanityCheck[];

    original ← LOOPHOLE[table.maxLink];

    IF table.base = NIL THEN interval ← [NIL, firstTablePages]
    ELSE
      BEGIN
      interval ← Space.GetMapUnitAttributes[table.base].interval;
      interval.count ← interval.count + growTablePages;
      IF CommFlags.doDebug AND (interval.count > maxTableSize) THEN
        Driver.Glitch[RoutingTableScrambled];
      END;

    table.base ← Space.ScratchMap[interval.count, tableUsage];  --allocate new
    IF original # 0 THEN
      Inline.LongCOPY[to: table.base, from: interval.pointer, nwords: original];

    IF interval.pointer # NIL THEN [] ← Space.Unmap[interval.pointer, return];

    table.base[table.maxLink] ← [];  --default first entry of new segment

    table.maxLink ← LOOPHOLE[  --compute new biggest value
      ((CARDINAL[interval.count] * Environment.wordsPerPage) /
      SIZE[TableElement]) * SIZE[TableElement]];
    stretch ← LOOPHOLE[table.maxLink, CARDINAL] - original;  --we added this much

    Inline.LongCOPY[  --ripple those suckers in there
      from: table.base + original,
      to: table.base + original + SIZE[TableElement],
      nwords: stretch - SIZE[TableElement]];

    IF CommFlags.doDebug THEN SanityCheck[];

    END;  --Expand


  Fill: PROC[maxDelay: CARDINAL ← Router.infinity] =
    BEGIN
    InsertIntoTable: ENTRY PROC[b: NSBuffer.Buffer] = INLINE
      {[] ← UpdateRoutingTable[b]};
    SendOneRequest: PROC[destination: System.NetworkNumber] =
      BEGIN
      nsb: NSBuffer.Body;
      b: NSBuffer.Buffer;
      timeIn: LONG CARDINAL;
      cH: Socket.ChannelHandle ← Socket.Create[
	System.nullSocketNumber, 1, 10, routingInformation];
      Socket.SetWaitTime[cH, 1000];  --only want to wait short times
      BEGIN
      ENABLE UNWIND => Socket.Delete[cH];  --client tired of waiting?
      b ← Socket.GetSendBuffer[cH];  --just one buffer, please
      nsb ← b.ns;  --and then get a local cache of b.ns
      nsb.destination ← him;  --send it to him 
      nsb.packetType ← routingInformation;  --we want information
      nsb.routingType ← routingInfoRequest;  --so we ask nicely
      nsb.routingTuple[0] ← [destination, Router.infinity];  --just for grins
      Socket.SetPacketBytes[
        b, NSTypes.bytesPerRoutingHeader +
	  Environment.bytesPerWord * SIZE[NSTypes.RoutingInfoTuple]];
      <<
      Thre is no reason this should be a Router.Broadcast when the destination
      is a multicast. If there's no ethernet, then it will go on the phone line
      anyhow. If there is an ethernet, then it will certainly beat the phone
      line for response time, won't it?
      >>
      Socket.PutPacket[cH, b]; b ← NIL;  --it's on its way
      timeIn ← System.GetClockPulses[];  --this is when we start
      WHILE (System.GetClockPulses[] - timeIn) < dawdle DO
        b ← Socket.GetPacket[cH ! Socket.TimeOut => LOOP];
	him ← b.ns.source;  --next time we'll be using just him
	IF destination = System.nullNetworkNumber THEN
	  {NSBuffer.ReturnBuffer[b]; EXIT};  --get rid of buffer and bail out
	InsertIntoTable[b];  --stick it in the real table
	NSBuffer.ReturnBuffer[b];  --remember to free the buffer 
        ENDLOOP;  --WHILE (System.GetClockPulses[] - timeIn) < dawdle DO
      END;
      Socket.Delete[cH];  --gun the socket - clean up the queue
      END;

    dawdle: LONG CARDINAL;
    him: System.NetworkAddress;

    SELECT TRUE FROM
      (maxDelay = 0) => IF (TestAndSet[-1] = 0) THEN table.fill ← 0;
      (maxDelay > table.fill) =>
	BEGIN
	[] ← TestAndSet[+1];  --count new user
	dawdle ← System.MicrosecondsToPulses[2D6];  --waiting for answers
	table.fill ← maxDelay;  --record the max ever requested
	him ← [
	  table.me.net,
	  System.broadcastHostNumber,
	  NSConstants.routingInformationSocket];
	SendOneRequest[table.me.net];  --will reset 'him'
	SendOneRequest[endEnum];  --talks only to 'him'
	END;
      ENDCASE => [] ← TestAndSet[+1];  --count new user

    END;  --Fill

  FindLocalNetID: <<PUBLIC>> ENTRY PROC [destNetNum: System.NetworkNumber]
    RETURNS [localNet: System.NetworkNumber] =
    BEGIN
    e: Entry;
    localNet ← IF (e ← FindElement[destNetNum, FALSE]) = NIL THEN
      System.nullNetworkNumber ELSE e.context.netNumber;
    IF localNet = System.nullNetworkNumber THEN
    --since System.nullNetworkNumber isn't helpful, find the first
    --network with a known network number and use it.
      FOR n: Device ← Driver.GetDeviceChain[], n.next UNTIL n = NIL DO
        c: RoutingTable.NetworkContext ← Protocol1.GetContext[n, ns];
	SELECT TRUE FROM
	  (c = NIL) => NULL;  --not even close
	  (~c.network.alive) => NULL;  --no better
	  (c.netNumber = System.nullNetworkNumber) => NULL;  --still bad
	  ENDCASE => {localNet ← c.netNumber; EXIT};  --reasonable substitute
        ENDLOOP;
    END;  --FindLocalNetID
    
  FindElement: INTERNAL PROC[net: NetworkNumber, sort: BOOLEAN]
    RETURNS[entry: Entry] =
    BEGIN
    prev, hash: TableRelative;
    SELECT TRUE FROM
      (net = System.nullNetworkNumber) => RETURN[NIL];
      (net = table.me.net) => RETURN[@table.me];
      (table.base = NIL) => RETURN[NIL];
      ENDCASE;
    IF CommFlags.doDebug THEN SanityCheck[];
    hash ← prev ← Hash[net.b];  --remember this value
    FOR link: TableRelative ← hash, table.base[link].rlink
      UNTIL link = endLink DO
      IF CommFlags.doDebug AND (link # hash) AND
        (table.base[link].net = System.nullNetworkNumber) THEN
          Driver.Glitch[RoutingTableScrambled];
      IF table.base[link].net = net THEN
        BEGIN
	entry ← @table.base[link];  --compute (maybe) return value
	SELECT TRUE FROM
	  (link = hash) => RETURN;  --#1 of list
	  (link = table.base[hash].rlink) => RETURN;  --#2 in list
	  (~sort) => RETURN;  --requested that we NOT sort the table
	  ENDCASE;  --needs sorting
	table.base[prev].rlink ← entry.rlink;  --remove 'link'
	entry.rlink ← table.base[hash].rlink;  --stick just after hash
	table.base[hash].rlink ← link;  --so it will be #2 next time
	IF CommFlags.doDebug THEN  --just check'n
	  BEGIN
	  SanityCheck[];
	  SELECT System.nullNetworkNumber FROM
	    entry.net => Driver.Glitch[RoutingTableScrambled];
	    table.base[hash].net => Driver.Glitch[RoutingTableScrambled];
	    table.base[prev].net => Driver.Glitch[RoutingTableScrambled];
	    ENDCASE;
	  END;
	RETURN;  --don't forget to get out
	END;
      prev ← link;  --remember last value
      ENDLOOP;
    RETURN[NIL];  --didn't find it
    END;  --FindElement
    
  FlushCache: <<PUBLIC>> ENTRY RoutingTable.FlushCacheProc =
    -- PROC [net: System.NetworkNumber]
    BEGIN
    -- Removes the entry with the specified net number from the routing
    -- table upon client request.  The request is ignored if there is no
    -- entry or if the entry is an attached net.
    RemoveElement[net];
    IF CommFlags.doStats THEN Stats.StatIncr[statCacheFlushed];
    END;  -- FlushCache
    
  Forward: PROC [b: NSBuffer.Buffer] =
    BEGIN
    IF b.ns.source.host # myHostID THEN
      RouterInternal.SendErrorPacket[b, cantGetThere, 0]
    ELSE
      {b.fo.status ← RouterInternal.XmitStatus[noRouteToNetwork];
      PutOnGlobalDoneQueue[b]};  --return b to the system buffer pool
    IF CommFlags.doStats THEN Stats.StatIncr[statNSNotForwarded];
    END;  --Forward

  Hash: PROC[n: CARDINAL] RETURNS[TableRelative] = INLINE
    {RETURN[LOOPHOLE[Inline.BITAND[n, hashMask] * SIZE[TableElement]]]};

  GetCurrentFill: PUBLIC <<RouterOps>> PROC RETURNS[NATURAL, NATURAL] =
    {RETURN[table.fill, table.users]};  
    
  GetDelay: PROC [net: NetworkNumber] RETURNS [delay: CARDINAL] =
    BEGIN
    -- Gets the delay to specified net.
    LockedFindNet: ENTRY PROC RETURNS[BOOLEAN] = INLINE
      BEGIN
      entry: Entry = FindElement[net, TRUE];
      IF entry = NIL THEN RETURN[FALSE]
      ELSE {delay ← entry.delay; RETURN[TRUE]};
      END;  --LockedFindNet
    
    IF net = System.nullNetworkNumber THEN RETURN[0];  --this is easy
    IF ~LockedFindNet[] THEN
      BEGIN
      --Try a cache fault to get the information.
      IF CommFlags.doDebug THEN
        BEGIN
	timein: LONG CARDINAL = System.GetClockPulses[];  --that's when it starts
	RoutingTableCacheFault[net];  --this could take time
	SELECT TRUE FROM
	  (LockedFindNet[]) => NULL;  --we got the answer
	  ((System.GetClockPulses[] - timein) < faultDally) =>
	    Driver.Glitch[CacheFaultFailure];
	  ENDCASE => ERROR Router.NoTableEntryForNet;
	END
      ELSE
        BEGIN
	RoutingTableCacheFault[net];  --this could take time (< faultDally).
	IF ~LockedFindNet[] THEN ERROR Router.NoTableEntryForNet;
	END;
      END;
    END;  --GetDelay

  GetRouteInfo: PUBLIC <<RouterOps>> ENTRY PROC[net: NetworkNumber]
    RETURNS[delay: CARDINAL, details: RouterOps.RouteDetails] =
    BEGIN
    device: Device;
    entry: Entry ← FindElement[net, FALSE];
    IF entry = NIL THEN RETURN WITH ERROR Router.NoTableEntryForNet;
    device ← entry.context.network;
    delay ← entry.delay;  --copy that one out
    details ← [
      driverType: device.device,
      driverNetwork: entry.net, statsPtr: device.stats,
      via: [entry.context.netNumber, entry.route, System.nullSocketNumber]];  
    END;  --GetRouteInfo

  
  ProbeINRs: PROC =
    BEGIN
    -- Does multiple BroadcastRoutingRequests to find out the network
    -- numbers, called at start time.
    b: NSBuffer.Buffer ← NIL;
    
    NullNetNum: ENTRY PROC RETURNS [BOOLEAN] =
      BEGIN
      --checks if any networks on device chain have null net numbers.
      FOR n: Device ← Driver.GetDeviceChain[], n.next UNTIL n = NIL DO
        c: RoutingTable.NetworkContext ← Protocol1.GetContext[n, ns];
	SELECT TRUE FROM
	  (c = NIL) => LOOP;  --what! a driver that doesn't support us!
	  (~c.network.alive) => LOOP;  --he would but he croaked
	  (c.netNumber = System.nullNetworkNumber) => RETURN[TRUE];
	  ENDCASE;
	ENDLOOP;
      RETURN [FALSE];
      END;  -- NullNetNum
      
    <<
    This could take a long time if we had trouble getting responses. (10 sec)
    This may be over-kill for one net that is still unnumbered, since
      a cache fault will force a broadcast on all nets.
    >>
    THROUGH [0..4) UNTIL pleaseStop DO
      IF NullNetNum[] THEN RoutingTableCacheFault[allNets] ELSE EXIT;
      ENDLOOP;
    END;  --ProbeINRs
        
       
  ProcessRoutingInfoPacket: PROC [b: NSBuffer.Buffer] =
    BEGIN
        
    ExamineResponsePacket: ENTRY PROC =
      BEGIN
      SELECT TRUE FROM
	(nsb.destination.host = myHostID) =>
	  BEGIN
	  IF CommFlags.doStats THEN Stats.StatIncr[statDirectedReceived];
	  IF (waitingDirectResp = 0) THEN NSBuffer.ReturnBuffer[b]
	  ELSE {NSBuffer.Enqueue[@requestedInfoQueue, b]; NOTIFY infoArrival};
	  END;
	ENDCASE =>  -- process gratuitous packet.
	  BEGIN
	  IF CommFlags.doStats THEN Stats.StatIncr[statGratReceived];
	  [] ← UpdateRoutingTable[b];
	  NSBuffer.ReturnBuffer[b];
	  END;
      END; -- of ExamineResponsePacket
      
    -- start of procedure
    nsb: NSBuffer.Body = b.ns; 
    incomingContext: RoutingTable.NetworkContext ← b.fo.context;

    SELECT TRUE FROM
      --interested only in routing protocol packets
      (nsb.packetType # routingInformation) => NULL;
      --can't learn anything new from ourselves
      (nsb.source.host = myHostID) => NULL;
      --sender should know himself
      (nsb.source.host = System.nullHostNumber) => NULL;
      --buffer didn't arrive through one of our drivers
      (incomingContext = NIL) => IF CommFlags.doDebug THEN
        Driver.Glitch[DriverDidntNoteNet];
      --we are not INR, so ignore routing requests
      (nsb.routingType = routingInfoRequest) => NULL;
      --not a request, not a response - so what is it?
      (nsb.routingType # routingInfoResponse) => NULL;
      --is the network it came in on alive?
      (~incomingContext.network.alive) => NULL;
      --did this come from our local net?
      (nsb.transportControl.hopCount = 0) =>
        BEGIN
	IF CommFlags.doStats THEN Stats.StatIncr[statNSGatewayPacketsRecv];
        ExamineResponsePacket[];
	RETURN; 
	END;
      ENDCASE;
    IF CommFlags.doStats THEN Stats.StatIncr[statJunkBroadcastNS];
    NSBuffer.ReturnBuffer[b];
    END;  -- ProcessRoutingInfoPacket
    
    
  RemoveElement: INTERNAL PROC[net: NetworkNumber] =
    BEGIN
    <<
    The entry we want deleted gets replaced by the .rlink entry and the .rlink
    entry gets marked empty.  That covers us in cases where the entry to be
    deleted is the one that's in the hash base, but it pushes the problem to
    the case removing from the end of the list.  For that case we have to
    keep track of the previous entry so we can change his .rlink to endLink.
    The ENDCASE is removing the one and only entry, and its the base.
    No notification is given of entries not found.
    >>
    prev, this, next: TableRelative;
    IF CommFlags.doDebug THEN SanityCheck[];
    IF table.base = NIL THEN RETURN;  --I claim that's as good as removed
    prev ← endLink;  --well known starting value
    FOR this ← Hash[net.b], table.base[this].rlink UNTIL this = endLink DO
      IF table.base[this].net # net THEN {prev ← this; LOOP};  --wrong entry
      IF (table.nEntries ← PRED[table.nEntries]) = 0 THEN
	BEGIN
	table.base ← Space.Unmap[table.base];  --we just gun the whole space
	table.maxLink ← nullLink; table.cache ← cacheHint;  --reset these
	EXIT;  --that's the quick and easy way to clean up
	END;
      next ← table.base[this].rlink;  --'next' is after entry to empty
      SELECT TRUE FROM
        (prev # endLink) =>  --in the middle or at the end
	  BEGIN
	  table.base[prev].rlink ← next;  --link 'prev' to 'next'; empty 'this'
	  END;
	(next # endLink) =>  --at the beginning and not a lone entry
	  BEGIN
	  table.base[this] ← table.base[next];  --copy 'next' on top of 'this'
	  this ← next;  --and then set up so that 'this' = 'next' gets emptied
	  END;
	ENDCASE;  --the one and only entry, and it's from the base

      table.base[this] ← [];  --emtpy 'this' entry
      table.cache ← MAX[cacheHint, MIN[table.cache, this]];
      EXIT;  --and, since we found what we're looking for....
      ENDLOOP;
    IF CommFlags.doDebug THEN SanityCheck[];
    END;  --RemoveElement

  RemoveDriver: ENTRY PROC [context: RoutingTable.NetworkContext] =
    BEGIN
    <<
    This procedure removes the specified attached network and all entries
    referencing it from the routing table. Multi entries may use this net.
    The loop doesn't increment the count on elements removed because the
    number of entries will be decremented by the "RemoveElement[entry.net]"
    statement.  In effect the number of entries is coming back to equal the
    number of elements counted.
    >>
    entry: Entry;
    count: NATURAL ← 0; 
    FOR entry ← @table.base[FIRST[TableRelative]], entry + SIZE[TableElement]
      UNTIL count = table.nEntries DO
      SELECT TRUE FROM
        (entry.context = NIL) => LOOP;  --don't increment count
        (entry.context = context) => RemoveElement[entry.net];
        ENDCASE => count ← SUCC[count];
      ENDLOOP;
    END;  --RemoveDriver

  RoutingTableActivate: ENTRY PROC = INLINE
    BEGIN
    myHostID ← Router.FindMyHostID[];
    table ← [];  --set initial values
    NSBuffer.QueueInitialize[@requestedInfoQueue];
    NSBuffer.QueueInitialize[@outQueue];
    END;  --RoutingTableActivate

 
  RoutingTableCacheFault: PROC [net: NetworkNumber] =
    BEGIN
    <<
    Broadcasts for info on specified network(s), waits for a directed response
    to be queued by ProcessRoutingInfoPacket, then searches for the desired
    tuple(s).  Called by RouterProcess, GetDelay or Fill.
    >>
    CacheFaultStart: ENTRY PROC = INLINE
      {waitingDirectResp ← SUCC[waitingDirectResp]};
    CacheFaultDone: ENTRY PROC = INLINE
     {IF (waitingDirectResp ← PRED[waitingDirectResp]) = 0 THEN
       NSBuffer.QueueCleanup[@requestedInfoQueue]};  --CacheFaultDone

    GatherDirectedResponses: ENTRY PROC RETURNS[done: BOOLEAN ← FALSE] =
      BEGIN
      <<
      Unlike the timer on the caller, this one is used to fix the amount of
      time between broadcasts requesting information.
      >>
      startBroadcast: LONG CARDINAL = System.GetClockPulses[];
      UNTIL done --OR timeout-- DO
        SELECT TRUE FROM
	  ((b ← NSBuffer.Dequeue[@requestedInfoQueue]) # NIL) =>
	    done ← UpdateRoutingTable[b, net];  --see if this fixes it
	  ((System.GetClockPulses[] - startBroadcast) > broadcastDally) =>
	    RETURN<<[FALSE]>>;  --and we had no buffer
	  ENDCASE => {WAIT infoArrival; LOOP};  --wait for some response
	NSBuffer.ReturnBuffer[b];  --get rid of buffer we dequeued
	ENDLOOP;
      END;  --GatherDirectedResponses

    b: NSBuffer.Buffer;
    nsb: NSBuffer.Body;
    startFault: LONG CARDINAL = System.GetClockPulses[];
    broadcastDally: LONG CARDINAL = Inline.DBITSHIFT[faultDally, -2];
    timesRequested, noBuffer: NATURAL ← 0;  --how many times did we try/fail?
    sizeRoutingRequest: NATURAL = Environment.bytesPerWord *
      (SIZE[routingInformation NSTypes.BufferBody] +
      SIZE[NSTypes.RoutingInfoTuple]);

    CacheFaultStart[];  --keep these packets around
         
    IF CommFlags.doStats THEN Stats.StatIncr[statCacheFaults];
    <<
    This loop will last until we find the answer, for some known period of
    time and we've asked the question at least twice.
    It is not dependent on the number of uninteresting responses received.
    This should ask the question no more than 4 times.
    >>
    UNTIL (timesRequested > 1) AND
      ((System.GetClockPulses[] - startFault) > faultDally) DO
      <<
      Broadcasts a routing information request on all attached networks.
      If <net> is supplied, the request will be for info on that net only, else
      information will be requested on all networks the routing 
      information suppliers know about.
      >>
      b ← NSBuffer.GetBuffer[myAccessHandle, send, FALSE, sizeRoutingRequest];
      IF b # NIL THEN
        BEGIN
	nsb ← b.ns;  --make a local copy
	nsb.packetType ← routingInformation;
	nsb.transportControl ← initialTransportControl;
	nsb.destination.socket ← nsb.source.socket ←
	  NSConstants.routingInformationSocket;
	nsb.pktLength ← sizeRoutingRequest;
	nsb.routingType ← routingInfoRequest;
	nsb.routingTuple[0] ← [net, Router.infinity];
	RouterInternal.BroadcastThisPacket[b];
	timesRequested ← timesRequested.SUCC;
	END
      ELSE IF CommFlags.doDebug THEN noBuffer ← noBuffer.SUCC;
      IF pleaseStop OR GatherDirectedResponses[] THEN EXIT;
      ENDLOOP;

    CacheFaultDone[];  --decrements count and flushes queue

    END;  --RoutingTableCacheFault
    
    
  RoutingTableDeactivate: ENTRY PROC = INLINE
    BEGIN
    pleaseStop ← TRUE;
    NSBuffer.QueueCleanup[@requestedInfoQueue];
    NSBuffer.QueueCleanup[@outQueue];
    END;  --RoutingTableDeactivate
    
    
  RoutingTableFork: SocketInternal.ListenerProcType =
    {ProcessRoutingInfoPacket[b]}; -- of RoutingTableFork
    
    
  RouterProcess: <<FORKED>> PROC =
    BEGIN
    <<
    This is the process that is poked by Transmit when a cache fault
    must be done before sending the buffer. It also runs the period check
    of the routing table to see if we can toss some old information out.
    >>
    
    DequeueLocked: ENTRY PROC RETURNS [NSBuffer.Buffer] = INLINE
      {RETURN[NSBuffer.Dequeue[@outQueue]]};

    b: NSBuffer.Buffer;

    UNTIL pleaseStop DO
      ENABLE ABORTED => EXIT;
      b ← WaitReqOrCheckTime[];  --wait for some work to do
      ProcessUsersRequest[b];  --then go off and do it
      ENDLOOP;
    UNTIL (b ← DequeueLocked[]) = NIL DO
      b.fo.status ← RouterInternal.XmitStatus[aborted];
      PutOnGlobalDoneQueue[b];  --requeue it
      IF CommFlags.doStats THEN Stats.StatIncr[statNSSentNowhere];
      ENDLOOP;
    END;  --RouterProcess
      
  WaitReqOrCheckTime: ENTRY PROC[] RETURNS[b: NSBuffer.Buffer] =
    BEGIN
    ENABLE UNWIND => NULL;
    <<
    This process services client transmit requests and also runs periodically
    to check the routing table for aged entries.
    >>
    now: LONG CARDINAL;
    WHILE outQueue.length = 0 DO
      WAIT routerCondition;  --wait for something to do
      IF table.base = NIL THEN LOOP;  --why bother?
      now ← System.GetClockPulses[];  --get the current time
      IF (now - timeOfLastCheck) > timeToCheck THEN
	{CheckRoutingTableEntries[]; timeOfLastCheck ← now};
      ENDLOOP;
    b ← NSBuffer.Dequeue[@outQueue];
    IF CommFlags.doDebug AND (b = NIL) THEN Driver.Glitch[NoBufferInQueue];
    END;  -- WaitReqOrCheckTime

  ProcessUsersRequest: PROC[b: NSBuffer.Buffer] =
    BEGIN
        
    MonitoredFindNet: ENTRY PROC RETURNS[BOOLEAN] = INLINE
      BEGIN
      entry: Entry = FindElement[net, TRUE];
      SELECT TRUE FROM
        (entry = NIL) => RETURN[FALSE];  --there's no such table entry
	(entry.delay = Router.infinity) => RETURN[FALSE];  --too far away
	ENDCASE;
      element ← entry↑;  --copy it out so we can use it safely
      entry.lastAccess ← System.GetClockPulses[];  --mark time last used
      RETURN[TRUE];
      END; -- of MonitoredFindNet
      
    -- start of procedure
    net: NetworkNumber;  --that's where he wants to go
    element: TableElement;  --our copy of the table element
    nextHost: HostNumber;  -- immediate destination to get him there.
    net ← b.ns.destination.net;  --that's where he's going
    RoutingTableCacheFault[net];  --crank up a fault
    IF CommFlags.doDebug THEN
      BEGIN
      timein: LONG CARDINAL = System.GetClockPulses[];  --that's when it starts
      RoutingTableCacheFault[net];  --crank up a fault
      SELECT TRUE FROM
	(MonitoredFindNet[]) => NULL;  --we got the answer
	((System.GetClockPulses[] - timein) < faultDally) =>
	  Driver.Glitch[CacheFaultFailure];
	ENDCASE =>
	  BEGIN
	  -- outgoing packet for unknown net - drop it.
	  b.fo.status ← RouterInternal.XmitStatus[noRouteToNetwork];
	  PutOnGlobalDoneQueue[b];  --get it back to caller | free
	  IF CommFlags.doStats THEN Stats.StatIncr[statNSSentNowhere];
	  RETURN;  --go back to caller
	  END;
      END
    ELSE
      BEGIN
      RoutingTableCacheFault[net];  --crank up a fault
      IF ~MonitoredFindNet[] THEN
	BEGIN
	-- outgoing packet for unknown net - drop it.
	b.fo.status ← RouterInternal.XmitStatus[noRouteToNetwork];
	PutOnGlobalDoneQueue[b];  --get it back to caller | free
	IF CommFlags.doStats THEN Stats.StatIncr[statNSSentNowhere];
	RETURN;  --go back to caller
	END;
      END;

    -- outgoing packet to be transmitted over the correct network
    nextHost ← IF element.route # System.nullHostNumber THEN element.route
      ELSE b.ns.destination.host; -- we are attached to the destination net
    b.fo.status ← RouterInternal.XmitStatus[goodCompletion];
    b.fo.context ← element.context;  --mark the context being used
    b.fo.network ← element.context.network; --mark the network used
    Protocol1.EncapsulateAndTransmit[LOOPHOLE[b], @nextHost];
    END;  -- ProcessUsersRequest

  Start: PROC =
    BEGIN  --This procedure turns the router on.
    priority: Process.Priority = Process.GetPriority[];  --save current
    pleaseStop ← FALSE;
    waitingDirectResp ← clientFills ← 0;
    RoutingTableActivate[];
    cH ← SocketInternal.CreateListen[
      socket: NSConstants.routingInformationSocket,
      callback: RoutingTableFork, clientData: NIL, 
      send: 1, receive: 10, type: routingInformation];
    myAccessHandle ← Socket.GetBufferPool[cH];
    Process.SetPriority[CommPriorities.receiver];  --let's get some cycles
    routerProcess ← FORK RouterProcess[];  --the guy that does cache faults
    Process.Detach[FORK ProbeINRs[]];  -- find out the network numbers.
    Process.SetPriority[priority];  --then back to whatever we started with
    END;  --Start


  Stop: PROC =
    BEGIN
    RoutingTableDeactivate[];
    Process.Abort[routerProcess];
    JOIN routerProcess[];
    Socket.Delete[cH];
    CleanUpRoutingTable[];
    END;  --Stop

  TableList: PUBLIC <<RouterOps>> ENTRY PROC[zone: UNCOUNTED ZONE]
    RETURNS[list: RouterOps.DetailList ← NIL] =
    BEGIN
    ENABLE UNWIND => NULL;  --incase the zone.NEW blows up
    entry: Entry;  --for a local copy of the table's entry
    device: Device;  --to get the opaque type where we can look
    index: NATURAL ← 0;  --to get into the sequence
    hashLink: TableRelative ← nullLink;  --to loop through the table
    IF table.base = NIL THEN RETURN;  --no table, no sequence, no worry
    <<
    This violates the rule of asking PILOT to do something for us while we
    hold are own monitor. But I don't want to worry about the table being
    a different size when we copy it than when we created the node to hold
    the copy. Guess we should warn users that this reduces some of the
    parallelism of the router.
    >>
    list ← zone.NEW[RouterOps.DetailSequence[table.nEntries + 1]];
    device ← table.me.context.network;
    list[index] ← [  --we're always first
      driverType: device.device, driverNetwork: table.me.context.netNumber,
      statsPtr: device.stats, via: System.nullNetworkAddress];
    THROUGH[0..hashLog) DO
      FOR rlink: TableRelative ← hashLink, entry.rlink
	UNTIL rlink = endLink DO
	entry ← @table.base[rlink];
	device ← entry.context.network;
	list[(index ← SUCC[index])] ← [driverType: device.device,
	  driverNetwork: entry.net, statsPtr: device.stats,
	  via: [entry.context.netNumber, entry.route, System.nullSocketNumber]];
	ENDLOOP;
      hashLink ← hashLink + SIZE[TableElement];  --get to next base
      ENDLOOP; 
    END;  --TableList

  Transmit: ENTRY PROC [b: NSBuffer.Buffer] =
    BEGIN
    <<
    Called to transmit a packet, this proc searches the routing table
    for the destination net.  If found, the proc sends the packet.  Because
    the client's process should not be used to do a cache fault, if the info
    is not found, the buffer is put on the outQueue and the sender process is 
    notified (which does the cache fault and sends the packet when the routing 
    info is obtained.  If the destination net is null, we simply shove it out
    on the first network on the chain.  In case of an abort, the caller owns
    the buffer.
    >>
    ENABLE UNWIND => NULL;
    entry: Entry;
    nextHost: HostNumber;
    nsb: NSBuffer.Body = b.ns;
        
    SELECT TRUE FROM
      (nsb.destination.net = System.nullNetworkNumber) =>
	BEGIN
	--running on net with no INR (using null net numbers).
	n: Device ← b.fo.network ← Driver.GetDeviceChain[];
	IF n = NIL OR ~n.alive THEN
	  BEGIN
	  --no network present, drop the packet.
	  b.fo.status ← RouterInternal.XmitStatus[noRouteToNetwork];
	  PutOnGlobalDoneQueue[b];  --give it back to system
	  IF CommFlags.doStats THEN Stats.StatIncr[statNSSentNowhere];
	  RETURN;
	  END;
	nextHost ← nsb.destination.host;
	END;
      (entry ← FindElement[nsb.destination.net, TRUE]) = NIL =>
	BEGIN
	<<
	No entry in table; tell RouterProcess to find one.
	But...
	  If this isn't a buffer being sent sourced from here AND
	  the number of buffers already hanging on the outQueue is
	  greater that 1, then forget it. Theory is that the buffers
	  on the queue are ones we're responding to (error or echo or
	  some variation of a swap source and destination).
	>>
	IF (b.fo.function # send) AND (outQueue.length > 1) THEN
	  NSBuffer.ReturnBuffer[b] ELSE NSBuffer.Enqueue[@outQueue, b];
	NOTIFY routerCondition;
	RETURN;
	END;
      (entry.delay < Router.infinity) =>
	BEGIN
	-- entry exists in table already.
	entry.lastAccess ← System.GetClockPulses[];  --mark the entry hot
	b.fo.context ← entry.context;  --mark the context being used
	b.fo.network ← entry.context.network; --mark the network being used
	-- outgoing packet to be transmitted over the correct network
	nextHost ← IF entry.route # System.nullHostNumber THEN entry.route 
	ELSE nsb.destination.host; -- we are attached to the destination net
	END;
      ENDCASE =>
	BEGIN
	--entry exists, but the destination net is not reachable. 
	b.fo.status ← RouterInternal.XmitStatus[noRouteToNetwork];
	PutOnGlobalDoneQueue[b];  --client may get it back
	IF CommFlags.doStats THEN Stats.StatIncr[statNSSentNowhere];
	RETURN;
	END;
    b.fo.status ← RouterInternal.XmitStatus[goodCompletion];
    Protocol1.EncapsulateAndTransmit[LOOPHOLE[b], @nextHost];
    END;  -- Transmit

  TestAndSet: ENTRY PROC[delta: INTEGER] RETURNS[users: NATURAL] =
   BEGIN
   RETURN[IF delta > 0 THEN (table.users ← table.users + 1)
     ELSE IF table.users > 0 THEN (table.users ← table.users - 1) ELSE 0];
   END;

  UpdateRoutingTable: INTERNAL PROC [
    b: NSBuffer.Buffer,
    destNetNum: System.NetworkNumber ← System.nullNetworkNumber]
    RETURNS [success: BOOLEAN ← FALSE] =
    <<
    Digs though tuples in packet and adds the interesting ones to the
    routing table.  "Interesting" tuples are ones with the desired 
    objectNetID.  Receivers of gratuitous info let it
    default to nullNetworkNumber.  <success>, used only by RoutingTable to
    find out if its info arrived, is set only if a new route is added (not
    if existing info is updated).
    >>

    BEGIN
    i: CARDINAL;
    tuples: CARDINAL;
    newDelay: CARDINAL;
    entry: Entry ← NIL;
    nsb: NSBuffer.Body = b.ns;
    tuple: NSTypes.RoutingInfoTuple;
    c: RoutingTable.NetworkContext = NARROW[b.fo.context];

    IF c.netNumber = System.nullNetworkNumber THEN  --do we understand life?
      c.netNumber ← nsb.source.net;  --copy net number to context
    IF table.me.net = System.nullNetworkNumber THEN
      table.me ← [net: nsb.source.net, context: b.fo.context];  --I'm special
    IF destNetNum = allNets THEN RETURN[TRUE];  --just wanted to know about me
    IF (table.fill = 0) AND (table.base = NIL)  --nothing's going to succeed
      AND (destNetNum = System.nullNetworkNumber) THEN RETURN;  --wasted time

    tuples ← (nsb.pktLength - NSTypes.bytesPerIDPHeader -
      (Environment.bytesPerWord * SIZE[NSTypes.RoutingInfoType])) /
      (Environment.bytesPerWord * SIZE[NSTypes.RoutingInfoTuple]);

    FOR i IN [0..tuples) DO
      tuple ← nsb.routingTuple[i];  --pick the tuple our for easy access
      newDelay ← Inline.BITAND[mask, tuple.interrouterDelay];  --strip high bits.

      SELECT TRUE FROM
	(tuple.objectNetID = allNets),
	(tuple.objectNetID = System.nullNetworkNumber) => NULL;
        ((entry ← FindElement[tuple.objectNetID, FALSE]) # NIL) =>
	  BEGIN
	  SELECT TRUE FROM
	    --Update the entry if this tuple has better/newer info.
	    (newDelay < entry.delay),    --it's better than what we know now
	    (entry.route = nsb.source.host),  --same router, longer path
	    (entry.age >= longerAge) =>  --it's worse, but newer
	      BEGIN
	      entry.delay ← newDelay;
	      entry.route ← nsb.source.host;
	      entry.context ← b.fo.context;
	      END;
	    ENDCASE;
	  entry.age ← youngster;  --the entry is young again
	  END;
	(tuple.objectNetID = destNetNum) =>  --trying to find new route
	  BEGIN
	  success ← newDelay < Router.infinity;  --maybe it was dead
	  entry ← AddElement[tuple.objectNetID];  --its never "me"
	  entry.delay ← newDelay;
	  entry.route ← nsb.source.host;
	  entry.context ← b.fo.context;
	  END;
	(newDelay <= table.fill) => --trying to fill
	  BEGIN
	  entry ← AddElement[tuple.objectNetID];  --its never "me"
	  entry.delay ← newDelay;
	  entry.route ← nsb.source.host;
	  entry.context ← b.fo.context;
	  END;
	ENDCASE;
      Process.Yield[];  --some to use, some to share
      ENDLOOP;
    END;  -- UpdateRoutingTable

        
  --initialization

  Process.EnableAborts[@routerCondition];
  Process.SetTimeout[@routerCondition, Process.MsecToTicks[26000]];
  Process.SetTimeout[@infoArrival, Process.MsecToTicks[350]];
  
  END.  --RoutingTableImpl module.

LOG
17-May-84 11:10:42  AOF  Post Klamath.
 2-Apr-85 16:40:38  AOF  Restarting vanilla routing after doing something else.
25-Jul-85  9:24:16  AOF  NIL context check in NullNetNum.
26-Jul-85 13:14:57  AOF  Don't WAIT on buffers in BroadcastRoutingRequest.
23-Oct-85 18:34:55  AOF  Make CacheFaults take fixed period of time.
 3-Nov-85 11:14:49  AOF  Rewrite of Fill and Enumerate.
10-Dec-85 17:21:15  AOF  Listener rework.
20-Dec-85 10:54:59  AOF  Forgot to monitor the new Enumerate code.
23-Jan-86 15:21:44  AOF  Decision to use Main or Aside table backwards.
 3-Feb-86 17:46:31  SMA  Don't remove entries for attached nets, sanity checking.
 4-Feb-86 11:30:53  AOF  Don't build aside table, use real one
 6-Feb-86 18:25:01  AOF  Allocate router object from heap, not frame
25-Feb-86 13:30:15  AOF  Rewrite table access method and fix GetDelay
22-May-86 18:24:54  SMA  No dependencies on Buffer, Driver.Network => Device.
 8-Jun-86 13:17:01  AOF  40 just wasn't big enough for testing list lengths
18-Jun-86 15:37:10  AOF  Sort table's links in FindElement
18-Aug-86 18:05:51  AOF  Local caching of b.ns in nsb.
10-Sep-86 14:23:19  AOF  Check for table.base = NIL when stopping router.
16-Nov-86 16:02:15  AOF  Add bool to NOT sort table entries in FindElement.
12-Jan-87 14:17:48  AOF  Debugging code for smashed table entry.
21-Jan-87 16:53:14  AOF  Aging of entries w/o new routing information.
26-Jan-87 11:54:19  WIrish  More tweeking of aging of entries w/o new routing information.
26-Jan-87 11:54:19  AOF  Using internal process to age tables
29-Jan-87 20:40:18  AOF  Gunned "CountThemSuckers"
10-Feb-87 15:48:54  AOF  Don't Glitch when we receive a null network answer.
 6-Mar-87 11:52:52  AOF  More of the same as above
11-Jun-87 16:40:16  AOF  Move rto back into global frame
28-Aug-87  9:17:30  AOF  Chasing CHS's table munge and "noRoute" problems
 1-Oct-87 17:54:37  AOF  Up priority of cache fault process
 9-Oct-87 11:53:18  AOF  ...but to "receiver" priority, not "realtime"
18-Oct-87 10:35:27  AOF  Better computation of max table size
20-Oct-87 19:35:53  AOF  AR#12150: Cache fault missing answers
21-Oct-87 19:16:06  AOF  Forgetting to delete socket on UNWIND in $Fill (CHS)
 6-Nov-87 17:37:53  AOF  No more mr. nice guy. Keep priority up and get job done
 7-Jan-88 18:48:30  AOF  Don't delete entries across transient circuits