ArpaEthernetTranslation.mesa
Copyright Ó 1987 by Xerox Corporation. All rights reserved.
John Larson, August 20, 1987 4:07:19 pm PDT
Demers, October 5, 1987 5:22:07 pm PDT
Adapted from XNSEthernetOneTranslation.mesa. See the Address Resolution Protocol (ARP) spec RFC826.TXT for more details.
DIRECTORY
Arpa USING [Address],
ArpaExtras USING [broadcastAddress, BroadcastAddressOnSubnetWithMask, IsBroadcastWithMask],
ArpaTranslation USING [DetermineAddressAndSubnetMaskForInterface, GetSubnetMask, GetTranslationTable, PutTranslationTable],
Basics USING [HWORD, Card32FromF, DoubleOr, DoubleNot],
BasicTime USING [GetClockPulses, MicrosecondsToPulses, Pulses],
CommBuffer USING [Overhead],
CommDriver USING [AllocBuffer, Buffer, FreeBuffer, GetNetworkChain, InsertReceiveProc, Network, RecvProc],
CommDriverType USING [Encapsulation],
Process USING [MsecToTicks, priorityForeground, SecondsToTicks, SetPriority, SetTimeout, Ticks],
XNS USING [broadcastHost, GetThisHost, Host, unknownHost];
ArpaEthernetTranslation: CEDAR MONITOR
LOCKS cH USING cH: Cache
IMPORTS ArpaExtras, ArpaTranslation, Basics, BasicTime, CommDriver, Process, XNS
EXPORTS CommBuffer
~ {
Buffer: TYPE ~ CommDriver.Buffer;
Network: TYPE ~ CommDriver.Network;
Encapsulation: PUBLIC TYPE ~ CommDriverType.Encapsulation; -- exported to CommBuffer
thisHost: XNS.Host ~ XNS.GetThisHost[];
allHosts: Arpa.Address ~ ArpaExtras.broadcastAddress;
Time
Pulses: TYPE ~ BasicTime.Pulses;
MSecsToPulses: PROC [n: CARD] RETURNS [Pulses] ~ INLINE {
RETURN [BasicTime.MicrosecondsToPulses[1000*n]] };
PulsesSince: PROC [then: Pulses] RETURNS [Pulses] ~ INLINE {
RETURN [BasicTime.GetClockPulses[] - then] };
Ethernet ARP Request / Reply Packets
HardwareType: TYPE ~ Basics.HWORD;
ethernet: HardwareType ~ [00H, 01H];
HardwareAddressLength: TYPE ~ BYTE;
ethernetAddressLength: HardwareAddressLength ~ BYTE[06H]; -- 6 bytes = 48 bits
ProtocolType: TYPE ~ Basics.HWORD;
ipType: ProtocolType ~ [08H, 00H]; -- ARPA IP type from Assigned Numbers RFC
ProtocolAddressLength: TYPE ~ BYTE;
ipAddressLength: ProtocolAddressLength ~ BYTE[04H]; -- 4 bytes
TranslationType: TYPE ~ Basics.HWORD; -- opcode in RFC826
requestType: TranslationType ~ [00H, 01H];
replyType: TranslationType ~ [00H, 02H];
HostPair: TYPE ~ MACHINE DEPENDENT RECORD [
nsHost: XNS.Host,
arpaHost: Arpa.Address];
TranslationPacketObject: TYPE ~ MACHINE DEPENDENT RECORD [
hardwareType: Basics.HWORD,
protocolType: Basics.HWORD,
hardwareAddressLength: BYTE,
protocolAddressLength: BYTE,
translationType: TranslationType,
senderHostPair: HostPair,
targetHostPair: HostPair];
translationPacketBytes: CARDINAL ~ BYTES[TranslationPacketObject]; -- Must be even!
TranslationBuffer: TYPE ~ REF TranslationBufferObject;
TranslationBufferObject: TYPE ~ MACHINE DEPENDENT RECORD [
ovh: CommBuffer.Overhead,
hardwareType: Basics.HWORD,
protocolType: Basics.HWORD,
hardwareAddressLength: BYTE,
protocolAddressLength: BYTE,
translationType: TranslationType,
senderHostPair: HostPair,
targetHostPair: HostPair];
Translation Entry Cache
For the Arpa world, the number of hash headers has been set to the maximum number of Pup hosts possible on an ethernet. The hash table chained overflow code is not exercised, and could be discarded. If you want to reduce the number of hash headers, replace the Identity hash function with something like the MOD function in the comment below.
numHashHeaders: CARDINAL ~ 256;
HashIndex: TYPE ~ [0..numHashHeaders);
Hash: PROC [arpaHost: Arpa.Address] RETURNS [HashIndex] ~ INLINE {
RETURN [arpaHost] };
Hash: PROC [arpaHost: Arpa.Address] RETURNS [HashIndex] ~ INLINE {
RETURN [ Basics.Card32FromF[LOOPHOLE[arpaHost]] MOD numHashHeaders ] };
Cache: TYPE ~ REF CacheObject;
CacheObject: TYPE ~ MONITORED RECORD [
daemon: PROCESS,
event: CONDITION,
newPendingEntry: BOOLFALSE,
sweepTime: Pulses,
sendHead, sendTail: Buffer,
broadcastHostEntry: CacheEntry,
thisHostEntry: CacheEntry,
pendingEntries: CacheEntry,
validEntries: ARRAY HashIndex OF CacheEntry];
CacheEntry: TYPE ~ REF CacheEntryObject;
CacheEntryObject: TYPE ~ RECORD [
next: CacheEntry,
hosts: HostPair,
whenToSend: Pulses,
timeToLive: CARDINAL
];
UpToDate: PROC [eH: CacheEntry] RETURNS [BOOL]
~ INLINE { RETURN [eH.timeToLive > 0] };
Timeouts
pulsesPerSweep: Pulses ← MSecsToPulses[19000];
sweepTimeout: Process.Ticks ← Process.SecondsToTicks[20];
sweepsToLive: CARDINAL ← 6;
pulsesPerResend: Pulses ~ MSecsToPulses[230];
resendTimeout: Process.Ticks ← Process.MsecToTicks[250];
sendsToLive: CARDINAL ← 8;
Encapsulating Arpa Packets
Statistics
noTranslation: INT ← 0;
notQuick: INT ← 0;
GetEncapsulation: PROC [network: Network, arpaHost: Arpa.Address] RETURNS [Encapsulation] ~ {
cH: Cache ← NARROW[ArpaTranslation.GetTranslationTable[network]];
eH: CacheEntry ← NIL;
subnetMask: Arpa.Address ← ArpaTranslation.GetSubnetMask[network];
hashIndex: HashIndex ~ Hash[arpaHost];
???? broadcastHost: Arpa.Address ← LOOPHOLE[Basics.DoubleOr[LOOPHOLE[ArpaTranslation.GetNet[network]], Basics.DoubleNot[LOOPHOLE[ArpaTranslation.GetSubnetMask[network]]]]]; ????
broadcastHost: Arpa.Address ← ArpaExtras.BroadcastAddressOnSubnetWithMask[network.arpa.host, subnetMask];
BEGIN
Quick check of first couple of entries without acquiring ML.
IF (eH ← cH.validEntries[hashIndex]) # NIL THEN {
IF (eH.hosts.arpaHost = arpaHost) AND UpToDate[eH] THEN GOTO Found;
IF (eH ← eH.next) # NIL THEN {
IF (eH.hosts.arpaHost = arpaHost) AND UpToDate[eH] THEN GOTO Found;
NULL; -- more checks would go here ...
};
};
IF ArpaExtras.IsBroadcastWithMask[arpaHost, subnetMask] THEN { eH ← cH.broadcastHostEntry; GOTO Found };
???? IF allHosts = LOOPHOLE[Basics.DoubleOr[LOOPHOLE[arpaHost], LOOPHOLE[ArpaTranslation.GetSubnetMask[network]]]] THEN { eH ← cH.broadcastHostEntry; GOTO Found }; ????
IF arpaHost = network.arpa.host THEN { eH ← cH.thisHostEntry; GOTO Found };
notQuick ← notQuick.SUCC;
IF (eH ← GetCacheEntry[cH, hashIndex, arpaHost]) # NIL THEN GOTO Found;
GOTO NotFound;
EXITS
Found => {
TRUSTED { RETURN[ [ethernet[ethernetDest~eH.hosts.nsHost, ethernetSource~thisHost, ethernetType~arpa]] ] }
};
NotFound => {
noTranslation ← noTranslation.SUCC;
TRUSTED { RETURN[ [ethernet[ethernetDest~XNS.unknownHost, ethernetSource~thisHost, ethernetType~translationFailed]] ] }
};
END;
};
GetCacheEntry: ENTRY PROC [cH: Cache, hashIndex: HashIndex, arpaHost: Arpa.Address] RETURNS [CacheEntry] ~ {
Search for a valid cache entry for the given nsHost. If a valid entry is found, return it; otherwise return NIL and arrange for an entry to be added.
eH, prevH: CacheEntry;
eH ← cH.validEntries[hashIndex]; prevH ← NIL;
WHILE eH # NIL DO
IF eH.hosts.arpaHost = arpaHost THEN {
IF UpToDate[eH]
THEN {
Move entry to head of list.
IF prevH # NIL THEN {
prevH.next ← eH.next;
eH.next ← cH.validEntries[hashIndex];
cH.validEntries[hashIndex] ← eH };
RETURN[eH] }
ELSE {
Entry needs to be refreshed — move it to pending list.
IF prevH # NIL
THEN prevH.next ← eH.next
ELSE cH.validEntries[hashIndex] ← eH.next;
eH.timeToLive ← sendsToLive;
eH.whenToSend ← BasicTime.GetClockPulses[];
eH.next ← cH.pendingEntries;
cH.pendingEntries ← eH;
cH.newPendingEntry ← TRUE; NOTIFY cH.event;
RETURN[eH] };
};
prevH ← eH; eH ← eH.next
ENDLOOP;
Search for a pending entry.
FOR eH ← cH.pendingEntries, eH.next WHILE eH # NIL DO
IF eH.hosts.arpaHost = arpaHost THEN
RETURN[IF eH.hosts.nsHost # XNS.unknownHost THEN eH ELSE NIL];
ENDLOOP;
TRUSTED { cH.pendingEntries ← NEW[ CacheEntryObject ← [next~cH.pendingEntries, hosts~[nsHost~XNS.unknownHost, arpaHost~arpaHost], whenToSend~BasicTime.GetClockPulses[], timeToLive~sendsToLive] ] };
cH.newPendingEntry ← TRUE; NOTIFY cH.event;
RETURN[NIL] };
Building Request / Reply Packets
MakeRequest: PROC [cH: Cache, arpaHost: Arpa.Address, sendTo: XNS.Host ← XNS.broadcastHost] RETURNS [b: Buffer] ~ {
Allocate a buffer, build a request packet in it, and return it.
The sendTo parameter is the XNS Host to which the request packet will be sent. It should be broadcastHost for a normal request.
bH: TranslationBuffer;
b ← CommDriver.AllocBuffer[];
TRUSTED { bH ← LOOPHOLE[b] };
bH.hardwareType ← ethernet;
bH.protocolType ← ipType;
bH.hardwareAddressLength ← ethernetAddressLength;
bH.protocolAddressLength ← ipAddressLength;
bH.translationType ← requestType;
bH.targetHostPair ← [nsHost~XNS.unknownHost, arpaHost~arpaHost];
bH.senderHostPair ← cH.thisHostEntry.hosts;
TRUSTED { bH.ovh.encap ← Encapsulation[ethernet[ethernetDest~sendTo, ethernetSource~thisHost, ethernetType~arp]] };
};
ConvertToReply: PROC [cH: Cache, bH: TranslationBuffer] ~ {
Given a request buffer, convert it to the corresponding reply.
Fill in the encapsulation part here, so the buffer can be sent using network.sendTranslate rather than network.return.
-- These 4 lines might not be needed but ...
bH.hardwareType ← ethernet;
bH.protocolType ← ipType;
bH.hardwareAddressLength ← ethernetAddressLength;
bH.protocolAddressLength ← ipAddressLength;
bH.translationType ← replyType;
bH.targetHostPair ← bH.senderHostPair;
bH.senderHostPair ← cH.thisHostEntry.hosts;
TRUSTED { bH.ovh.encap ← Encapsulation[ethernet[ethernetDest~bH.targetHostPair.nsHost, ethernetSource~thisHost, ethernetType~arp]] };
};
Processing Received Translation Packets
AddTranslation: ENTRY PROC [cH: Cache, hosts: HostPair] ~ {
eH, prevH: CacheEntry;
i: HashIndex ~ Hash[hosts.arpaHost];
Look for a pending entry.
eH ← cH.pendingEntries; prevH ← NIL;
WHILE eH # NIL DO
IF eH.hosts.arpaHost = hosts.arpaHost THEN {
IF prevH = NIL THEN cH.pendingEntries ← eH.next ELSE prevH.next ← eH.next;
eH.hosts.nsHost ← hosts.nsHost;
EXIT };
prevH ← eH; eH ← eH.next
ENDLOOP;
If no pending entry, look for a valid one.
IF eH = NIL THEN {
eH ← cH.validEntries[i]; prevH ← NIL;
WHILE eH # NIL DO
IF eH.hosts.arpaHost = hosts.arpaHost THEN {
IF prevH = NIL THEN cH.validEntries[i] ← eH.next ELSE prevH.next ← eH.next;
If existing entry is incorrect, drop it on the floor ...
IF eH.hosts.nsHost # hosts.nsHost THEN eH ← NIL;
EXIT };
prevH ← eH; eH ← eH.next
ENDLOOP;
};
IF eH = NIL
THEN eH ← NEW[ CacheEntryObject ← [next~, hosts~hosts, whenToSend~, timeToLive~]];
eH.timeToLive ← sweepsToLive;
eH.next ← cH.validEntries[i];
cH.validEntries[i] ← eH;
};
Receive Statistics
requestsReceived: INT ← 0;
repliesReceived: INT ← 0;
tooShort: INT ← 0;
badProtocol: INT ← 0;
RecvTranslation: CommDriver.RecvProc
[network: Network, buffer: Buffer, bytes: NAT] RETURNS [Buffer]
~ {
cH: Cache ← NARROW[ArpaTranslation.GetTranslationTable[network]];
bH: TranslationBuffer;
IF bytes < translationPacketBytes THEN {
tooShort ← tooShort.SUCC;
RETURN [buffer] };
TRUSTED { bH ← LOOPHOLE[buffer] };
SELECT TRUE FROM
bH.translationType = requestType => {
IF bH.targetHostPair.arpaHost = network.arpa.host THEN {
requestsReceived ← requestsReceived.SUCC;
AddTranslation[cH, bH.senderHostPair];
ConvertToReply[cH, bH];
EnqueueForSending[cH, buffer];
buffer ← NIL;
};
};
bH.translationType = replyType => {
repliesReceived ← repliesReceived.SUCC;
AddTranslation[cH, bH.senderHostPair];
};
ENDCASE => {
badProtocol ← badProtocol.SUCC };
RETURN[buffer];
};
Daemon Process
EnqueueForSending: ENTRY PROC [cH: Cache, b: Buffer] ~ {
IF cH.sendHead = NIL THEN cH.sendHead ← b ELSE cH.sendTail.ovh.next ← b;
cH.sendTail ← b;
b.ovh.next ← NIL;
NOTIFY cH.event };
InternalEnqueueForSending: INTERNAL PROC [cH: Cache, b: Buffer] ~ {
IF cH.sendHead = NIL THEN cH.sendHead ← b ELSE cH.sendTail.ovh.next ← b;
cH.sendTail ← b;
b.ovh.next ← NIL;
NOTIFY cH.event };
DequeueForSending: ENTRY PROC [cH: Cache] RETURNS [b: Buffer] ~ {
IF (b ← cH.sendHead) = NIL THEN RETURN;
IF (cH.sendHead ← NARROW[b.ovh.next]) = NIL THEN cH.sendTail ← NIL;
};
InternalSendQueueIsEmpty: INTERNAL PROC [cH: Cache] RETURNS [BOOL] ~ INLINE {
RETURN [cH.sendHead = NIL] };
sweepsInhibited: BOOLFALSE; -- DEBUG
WaitAndScanCache: ENTRY PROC [cH: Cache] ~ {
eH, prevH: CacheEntry;
IF InternalSendQueueIsEmpty[cH] AND NOT cH.newPendingEntry THEN {
TRUSTED { IF cH.pendingEntries # NIL
THEN Process.SetTimeout[@cH.event, resendTimeout]
ELSE Process.SetTimeout[@cH.event, sweepTimeout] };
WAIT cH.event };
prevH ← NIL; eH ← cH.pendingEntries;
WHILE eH # NIL DO
IF PulsesSince[eH.whenToSend] >= 0 THEN {
IF eH.timeToLive = 0 THEN {
Delete the entry.
eH ← eH.next;
IF prevH = NIL THEN cH.pendingEntries ← eH ELSE prevH.next ← eH;
LOOP };
{
Send the entry
destHost: XNS.Host ~ IF (eH.timeToLive > (sendsToLive/2)) AND (eH.hosts.nsHost # XNS.unknownHost) THEN eH.hosts.nsHost ELSE XNS.broadcastHost;
buffer: Buffer ~ MakeRequest[cH, eH.hosts.arpaHost, destHost];
InternalEnqueueForSending[cH, buffer];
eH.timeToLive ← eH.timeToLive - 1;
eH.whenToSend ← BasicTime.GetClockPulses[] + pulsesPerResend;
};
};
prevH ← eH; eH ← eH.next;
ENDLOOP;
cH.newPendingEntry ← FALSE;
IF (PulsesSince[cH.sweepTime] >= pulsesPerSweep) AND (NOT sweepsInhibited) THEN {
Do a sweep ...
FOR i: HashIndex IN [0..numHashHeaders) DO
FOR eH ← cH.validEntries[i], eH.next WHILE eH # NIL DO
IF eH.timeToLive > 0 THEN eH.timeToLive ← eH.timeToLive - 1;
ENDLOOP;
ENDLOOP;
cH.sweepTime ← BasicTime.GetClockPulses[];
};
};
Daemon: PROC [network: Network] ~ {
cH: Cache ← NARROW[ArpaTranslation.GetTranslationTable[network]];
buffer: Buffer;
Process.SetPriority[Process.priorityForeground];
DO
WaitAndScanCache[cH];
WHILE (buffer ← DequeueForSending[cH]) # NIL DO
network.arpa.sendTranslate[network, buffer, translationPacketBytes];
CommDriver.FreeBuffer[buffer];
ENDLOOP;
ENDLOOP;
};
Initialization
Init: PROC = {
Install a cache (and start a daemon) for each ethernet on the chain.
cH: Cache;
FOR network: Network ← CommDriver.GetNetworkChain[], network.next UNTIL network = NIL DO
ipBroadcastHost: Arpa.Address;
IF network.type # ethernet THEN LOOP;
IF NOT ArpaTranslation.DetermineAddressAndSubnetMaskForInterface[network].ok
THEN LOOP;
cH ← NEW[ CacheObject ← [sweepTime~BasicTime.GetClockPulses[]] ];
ipBroadcastHost ← LOOPHOLE[Basics.DoubleOr[LOOPHOLE[network.arpa.host], Basics.DoubleNot[LOOPHOLE[ArpaTranslation.GetSubnetMask[network]]]]];
cH.broadcastHostEntry ← NEW[ CacheEntryObject ← [hosts~[nsHost~XNS.broadcastHost, arpaHost~ipBroadcastHost], whenToSend~, timeToLive~]];
cH.thisHostEntry ← NEW[ CacheEntryObject ← [hosts~[nsHost~thisHost, arpaHost~network.arpa.host], whenToSend~, timeToLive~] ];
ArpaTranslation.PutTranslationTable[network, cH];
network.arpa.getEncapsulation ← GetEncapsulation;
CommDriver.InsertReceiveProc[network~network, type~arpaTranslate, proc~RecvTranslation];
cH.daemon ← FORK Daemon[network];
ENDLOOP;
};
Init[];
}.