-- File: RoutingTableImpl.mesa - last edit:
-- AOF 24-Feb-88 17:52:05
-- 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) => NULL;
((entry ← AddElement[context.netNumber]) = NIL) => RETURN; --null net
ENDCASE;
entry.context ← context; --finish loading the entry
SELECT TRUE FROM
(~CommFlags.doDebug) => NULL; --nobody cares
(entry.net = System.nullNetworkNumber) =>
Driver.Glitch[RoutingTableScrambled];
ENDCASE;
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
<<
Delete the entry if
o it is not a transient circuit and has received no recent updates
o the table isn't being filled and there are no recent accesses
This has the side affect of not aging transient entries, but transient
entries can still be deleted if they aren't being used. That's just in
case you get stuck with a very dismal forcast and want to retry your
luck.
>>
BEGIN
SELECT TRUE FROM
((entry.context.network.device < phonenet) --not transient
AND
((entry.age ← entry.age.SUCC) >= flushAge)) => GOTO delete; --old
(((System.GetClockPulses[] - entry.lastAccess) > tableLife) --unused
AND
(entry.delay > table.fill)) => GOTO delete; --not filling
ENDCASE => prev ← this; --keep the entry - chase the chain;
EXITS delete =>
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;
END;
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
body: 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
body ← b.ns; --and then get a local cache of b.ns
body.destination ← him; --send it to him
body.packetType ← routingInformation; --we want information
body.routingType ← routingInfoRequest; --so we ask nicely
body.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
(body.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
body: NSBuffer.Body = b.ns;
incomingContext: RoutingTable.NetworkContext ← b.fo.context;
SELECT TRUE FROM
--interested only in routing protocol packets
(body.packetType # routingInformation) => NULL;
--can't learn anything new from ourselves
(body.source.host = myHostID) => NULL;
--sender should know himself
(body.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
(body.routingType = routingInfoRequest) => NULL;
--not a request, not a response - so what is it?
(body.routingType # routingInfoResponse) => NULL;
--is the network it came in on alive?
(~incomingContext.network.alive) => NULL;
--did this come from our local net?
(body.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.
It also doesn't advance the entry pointer of an element is removed. That
means if it was removed, it may possible rescan the same entry and find
find context == NIL. But if RemoveElement had to copy a new element on
top of the one just deleted, we will look at it too.
>>
count: NATURAL ← 0;
entry: Entry ← @table.base[FIRST[TableRelative]];
<<
table.me has to be special cased. We want to reset it too, including
the network number. The net number will be filled in when the driver
is added again, if ever.
NB: What if it's a different net number?
>>
IF table.me.context # NIL --make sure we haven't already done this
AND table.me.context.network = context.network THEN table.me ← [];
UNTIL count = table.nEntries DO
SELECT TRUE FROM
(entry.context = NIL) => entry ← entry + SIZE[TableElement];
(entry.context.network = context.network) => RemoveElement[entry.net];
ENDCASE => {count ← SUCC[count]; entry ← entry + SIZE[TableElement]};
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;
body: 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
body ← b.ns; --make a local copy
body.packetType ← routingInformation;
body.transportControl ← initialTransportControl;
body.destination.socket ← body.source.socket ←
NSConstants.routingInformationSocket;
body.pktLength ← sizeRoutingRequest;
body.routingType ← routingInfoRequest;
body.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;
body: NSBuffer.Body = b.ns;
SELECT TRUE FROM
(body.destination.net = System.nullNetworkNumber) =>
BEGIN
--running on net with no INR (using null net numbers).
device: Device ← b.fo.network ← Driver.GetDeviceChain[];
SELECT TRUE FROM
(device = NIL), --there are no devices on the chain
(~device.alive), --the first one isn't alive
((b.fo.context ← Protocol1.GetContext[device, ns]) = NIL) =>
--that device doesn't support ns--
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; --get out of here
END;
ENDCASE;
nextHost ← body.destination.host; --the destination is immedate
END;
(entry ← FindElement[body.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;
((b.fo.context ← entry.context) = NIL) =>
BEGIN
--the driver behind this route has been deleted
--assertion: this is local network access via table.me
b.fo.status ← RouterInternal.XmitStatus[noRouteToNetwork];
PutOnGlobalDoneQueue[b]; --client may get it back
IF CommFlags.doStats THEN Stats.StatIncr[statNSSentNowhere];
RETURN;
END;
(entry.delay < Router.infinity) =>
BEGIN
-- entry exists in table already.
entry.lastAccess ← System.GetClockPulses[]; --mark the entry hot
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 body.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;
body: 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 ← body.source.net; --copy net number to context
IF table.me.net = System.nullNetworkNumber THEN
table.me ← [net: body.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 ← (body.pktLength - NSTypes.bytesPerIDPHeader -
(Environment.bytesPerWord * SIZE[NSTypes.RoutingInfoType])) /
(Environment.bytesPerWord * SIZE[NSTypes.RoutingInfoTuple]);
FOR i IN [0..tuples) DO
tuple ← body.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 = body.source.host), --same router, longer path
(entry.age >= longerAge) => --it's worse, but newer
BEGIN
entry.delay ← newDelay;
entry.route ← body.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 ← body.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 ← body.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 body.
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
20-Feb-88 15:53:56 AOF Assigning b.fo.context for null nets in $Transmit
24-Feb-88 1:51:08 AOF RemoveDriver fixup, deleting old transients