-- File: Arpa10MBitImpl.mesa - last edit:
-- AOF 25-Mar-87 11:28:09
-- JAV 20-Nov-86 15:26:40
-- SMA 5-Jun-86 11:02:23
-- Copyright (C) 1985, 1986, 1987 by Xerox Corporation. All rights reserved.
DIRECTORY
Arpa10MBit USING [],
ArpaBuffer USING [Body],
ArpaFlags USING [doDebug, doStats],
ArpaPortInternal USING [
AddrMatch, BuildMasks, GetArpaAddr, GetMyBroadcastAddr],
ArpaRouter USING [InternetAddress, unknownInternetAddress],
ArpaRoutingTable USING [ContextObject, NetworkContext],
ArpaStats USING [Incr],
ArpaTypes USING [InternetAddress],
Buffer USING [
AccessHandle, Buffer, DestroyPool, Device, GetBuffer, MakePool, Type],
CommHeap USING [zone],
CommPriorities USING [driver],
Driver USING [Device],
Environment USING [bytesPerWord],
EtherMAC USING [EncapObject, Encapsulation, EthernetPacketType],
HostNumbers USING [HostNumber, IsMulticastID, ProcessorID],
Process USING [
Abort, DisableTimeout, EnableAborts, SecondsToTicks, SetPriority, SetTimeout],
Protocol1 USING [DecapsulatorProc, EncapsulatorProc],
SpecialSystem USING [
broadcastHostNumber, GetProcessorID, HostNumber, nullHostNumber, ProcessorID],
System USING [GetClockPulses, MicrosecondsToPulses, Pulses];
Arpa10MBitImpl: MONITOR
IMPORTS
ArpaPortInternal, ArpaRouter, ArpaStats, HostNumbers, Process,
Buffer, CommHeap, SpecialSystem, System
EXPORTS Buffer, Arpa10MBit, ArpaRouter =
BEGIN
Device: PUBLIC <<Buffer>> TYPE = Driver.Device;
InternetAddress: PUBLIC <<ArpaRouter>> TYPE = ArpaTypes.InternetAddress;
bpw: NATURAL = Environment.bytesPerWord;
bytesInArp: NATURAL = SIZE[ArpBody] * bpw;
wordsOfEncapsulation: NATURAL = SIZE[EtherMAC.EncapObject];
bytesOfEncapsulation: NATURAL = SIZE[EtherMAC.EncapObject] * bpw;
InternetAddressPointer: TYPE = LONG POINTER TO ArpaTypes.InternetAddress;
pool: Buffer.AccessHandle; --created in $Create
broadcast: InternetAddress; --assigned in $Create
--ARP packet format.
ArpOp: TYPE = MACHINE DEPENDENT {request(1), reply(2)};
ArpBody: TYPE = MACHINE DEPENDENT RECORD [
hardware(0): CARDINAL, --hardware address space
protocol(1): EtherMAC.EthernetPacketType, --protocol address space
hrdAddrLen(2: 0..7): CARDINAL[0..256), --length of hardware address in bytes
prtAddrLen(2: 8..15): CARDINAL[0..256), --length of protocol address in bytes
op(3): ArpOp, --operation
senderEtherAddr(4): HostNumbers.HostNumber, --sender's 48-bit ether address
senderIpAddr(7): InternetAddress, --sender's protocol (IP) address
targetEtherAddr(9): SpecialSystem.HostNumber, --target's unknown 48-bit addr
targetIpAddr(12): InternetAddress]; --target's protocol (IP) address
TranslaterHandle: PUBLIC TYPE = LONG POINTER TO TranslaterObject;
TranslaterObject: PUBLIC TYPE = RECORD[
me, all, head: TranslateEntry ← NIL,
hmsk: InternetAddress, --based on me.
event: CONDITION, demon: PROCESS ← NIL];
TranslatePair: TYPE = LONG POINTER TO TranslateRecord;
TranslateRecord: TYPE = MACHINE DEPENDENT RECORD [
etherHost: SpecialSystem.HostNumber, arpaHost: InternetAddress];
TranslateEntry: TYPE = LONG POINTER TO TranslateObject;
TranslateObject: TYPE = RECORD [
nextLink: TranslateEntry,
translatePair: TranslateRecord,
tries: CARDINAL,
timeStamp: System.Pulses,
status: TranslateStatus];
TranslateStatus: TYPE = {
new, --new and unresolved, no request sent.
pending, --unresolved, request sent, reply pending.
active, --resolved
zombie}; --pending entry that we were unable to resolve.
ipAddrLen: CARDINAL = SIZE[InternetAddress] * bpw;
etherAddrLen: CARDINAL = SIZE[SpecialSystem.HostNumber] * bpw;
etherHardware: CARDINAL = 1; --cuz ARP spec says so.
retryLimit: CARDINAL = 8; --gotta stop somewhere
retryPulses: System.Pulses = System.MicrosecondsToPulses[2D6];
deactivatePulses: System.Pulses = System.MicrosecondsToPulses[18D7];
myEtherHost: SpecialSystem.ProcessorID = SpecialSystem.GetProcessorID[];
myArpaAddr: InternetAddress ← ArpaRouter.unknownInternetAddress;
Capsulators: PUBLIC <<Arpa10MBit>>PROC RETURNS[
decap: Protocol1.DecapsulatorProc, encap: Protocol1.EncapsulatorProc] =
{RETURN[DecapsulateArpaEthernet, EncapsulateArpaEthernet]};
CreateCapsulators: PUBLIC <<Arpa10MBit>> PROC[driver: Device]
RETURNS[xlate: TranslaterHandle] =
BEGIN
xlate ← CommHeap.zone.NEW[TranslaterObject ← [
hmsk: ArpaPortInternal.BuildMasks[myArpaAddr].hostMask]];
Process.EnableAborts[@xlate.event];
broadcast ← ArpaPortInternal.GetMyBroadcastAddr[];
xlate.all ← AddTranslateRecord[
xlate, [SpecialSystem.broadcastHostNumber, broadcast]];
xlate.me ← AddTranslateRecord[xlate, [myEtherHost, myArpaAddr]];
xlate.demon ← FORK Demon[driver, xlate];
pool ← Buffer.MakePool[1, 1]; --needs a pool to move
END; --Create
DestroyCapsulators: PUBLIC <<Arpa10MBit>> PROC[xlate: TranslaterHandle] =
BEGIN
IF xlate.demon # NIL THEN {Process.Abort[xlate.demon]; JOIN xlate.demon};
--cleanup in case demon was never running
UNTIL xlate.head = NIL DO
e: TranslateEntry ← xlate.head;
xlate.head ← e.nextLink;
CommHeap.zone.FREE[@e];
ENDLOOP;
Buffer.DestroyPool[pool]; pool ← NIL;
END; --Delete
EncapsulateArpaEthernet: PUBLIC <<Arpa10MBit>> Protocol1.EncapsulatorProc =
--EncapsulatorProc: TYPE = PROC[b: Buffer.Buffer, immediate: LONG POINTER];
BEGIN
context: ArpaRoutingTable.NetworkContext = NARROW[b.fo.context];
destination: InternetAddressPointer = NARROW[immediate];
protocol: TranslaterHandle = NARROW[context.protocol];
mask: InternetAddress = protocol.hmsk;
body: ArpaBuffer.Body = LOOPHOLE[b.highLayer.blockPointer];
e: EtherMAC.Encapsulation = LOOPHOLE[body - wordsOfEncapsulation];
etherHost: SpecialSystem.HostNumber ← IF ArpaPortInternal.AddrMatch[
mask, broadcast, body.ipHeader.destination] THEN
SpecialSystem.broadcastHostNumber
ELSE Translate[context.protocol, destination↑];
e↑ ← [etherHost, myEtherHost, arpa];
b.linkLayer ← [LOOPHOLE[e], 0, bytesOfEncapsulation];
b.fo.driver.length ← body.ipHeader.length + bytesOfEncapsulation;
END; --EncapsulateArpaEthernet
DecapsulateArpaEthernet: PUBLIC <<Arpa10MBit>> Protocol1.DecapsulatorProc =
--DecapsulatorProc: TYPE = PROC[b: Buffer.Buffer] RETURNS[Buffer.Type];
BEGIN
e: EtherMAC.Encapsulation = LOOPHOLE[b.linkLayer.blockPointer];
body: ArpaBuffer.Body = LOOPHOLE[e + wordsOfEncapsulation];
IF b.fo.driver.length < bytesOfEncapsulation THEN RETURN[orphan];
IF HostNumbers.IsMulticastID[LOOPHOLE[@e.ethernetSource]] THEN
RETURN[orphan]; --that's illegal from the source
SELECT e.ethernetType FROM
arp => {ReceiveTranslate[b]; RETURN[orphan]}; --one of those
arpa =>
BEGIN
bytes: CARDINAL = b.fo.driver.length - bytesOfEncapsulation;
IF ArpaFlags.doStats THEN ArpaStats.Incr[rawArpaRcvd];
b.linkLayer.stopIndexPlusOne ← wordsOfEncapsulation;
b.highLayer ← [LOOPHOLE[body], 0, body.ipHeader.length];
RETURN[IF bytes < body.ipHeader.length THEN orphan ELSE arpa];
END;
ENDCASE => RETURN[vagrant]; --still unknown
END; --DecapsulateArpaEthernet
Translate: ENTRY PROC[
xlate: TranslaterHandle, arpaHost: ArpaTypes.InternetAddress]
RETURNS [etherHost: SpecialSystem.HostNumber] =
BEGIN
e: TranslateEntry;
SELECT TRUE FROM
((e ← FindTranslate[xlate, arpaHost]) = NIL) =>
BEGIN
e ← CommHeap.zone.NEW[TranslateObject];
e.translatePair.arpaHost ← arpaHost;
e.nextLink ← xlate.head; xlate.head ← e;
NOTIFY xlate.event;
e.status ← new; e.tries ← 0;
etherHost ← SpecialSystem.nullHostNumber;
e.timeStamp ← System.GetClockPulses[];
END;
(e.status = active) =>
BEGIN
IF e # xlate.head THEN
BEGIN
--sort this element to head of linked list
RemoveTranslate[xlate, e];
e.nextLink ← xlate.head; xlate.head ← e;
END;
etherHost ← e.translatePair.etherHost;
e.timeStamp ← System.GetClockPulses[];
END;
(e.status = zombie) =>
BEGIN
IF e # xlate.head THEN
BEGIN
--sort this element to head of linked list
RemoveTranslate[xlate, e];
e.nextLink ← xlate.head; xlate.head ← e;
END;
NOTIFY xlate.event;
e.status ← new; e.tries ← 0;
etherHost ← SpecialSystem.nullHostNumber;
e.timeStamp ← System.GetClockPulses[];
END;
ENDCASE => etherHost ← SpecialSystem.nullHostNumber;
END; --Translate
--interface
FindTranslate: PROC[
xlate: TranslaterHandle, arpaHost: ArpaTypes.InternetAddress]
RETURNS [entry: TranslateEntry] =
BEGIN
mask: InternetAddress = ArpaPortInternal.BuildMasks[arpaHost].hostMask;
FOR entry ← xlate.head, entry.nextLink WHILE entry # NIL DO
IF ArpaPortInternal.AddrMatch[
mask, arpaHost, entry.translatePair.arpaHost] THEN RETURN;
ENDLOOP;
END;
AddTranslate: INTERNAL PROC[xlate: TranslaterHandle, entry: TranslateEntry] =
{entry.nextLink ← xlate.head; xlate.head ← entry}; --AddTranslate
RemoveTranslate: INTERNAL PROC[xlate: TranslaterHandle, entry: TranslateEntry] =
BEGIN
e, pred: TranslateEntry;
IF (pred ← xlate.head) = entry THEN
{xlate.head ← xlate.head.nextLink; RETURN};
FOR e ← pred.nextLink, e.nextLink UNTIL e = NIL DO
IF e # entry THEN pred ← e
ELSE {pred.nextLink ← entry.nextLink; EXIT};
ENDLOOP;
END;
AddTranslateRecord: ENTRY PROC[xlate: TranslaterHandle, pair: TranslateRecord]
RETURNS [e: TranslateEntry] =
BEGIN
SELECT (e ← FindTranslate[xlate, pair.arpaHost]) FROM
NIL =>
BEGIN
e ← CommHeap.zone.NEW[TranslateObject];
e.nextLink ← xlate.head; xlate.head ← e;
END;
xlate.all, xlate.me => RETURN;
ENDCASE;
e.translatePair ← pair; e.status ← active;
e.timeStamp ← System.GetClockPulses[];
END;
Demon: ENTRY PROC[network: Device, xlate: TranslaterHandle] =
BEGIN
SendRequest: INTERNAL PROC =
BEGIN
b: Buffer.Buffer ← Buffer.GetBuffer[, pool, send, FALSE, bytesInArp];
IF b # NIL THEN
BEGIN
ec: EtherMAC.Encapsulation ← LOOPHOLE[b.linkLayer.blockPointer];
body: LONG POINTER TO ArpBody ← LOOPHOLE[ec + wordsOfEncapsulation];
ec ↑ ← [SpecialSystem.broadcastHostNumber, myEtherHost, arp];
b.fo.driver.length ← bytesOfEncapsulation + bytesInArp;
b.linkLayer.stopIndexPlusOne ← bytesOfEncapsulation;
body↑ ← [
hardware: etherHardware, protocol: arpa, hrdAddrLen: etherAddrLen,
prtAddrLen: ipAddrLen, op: request,
senderEtherAddr: xlate.me.translatePair.etherHost,
senderIpAddr: xlate.me.translatePair.arpaHost,
targetEtherAddr: , targetIpAddr: e.translatePair.arpaHost];
network.sendRawBuffer[b];
IF ArpaFlags.doStats THEN ArpaStats.Incr[xlateReqSent];
END;
END; --SendRequest
age: System.Pulses;
e, nextE: TranslateEntry;
pendingEntries: BOOLEAN;
Process.SetPriority[CommPriorities.driver];
<<
It would appear that the outer loop is setting the timeout on the condition
variable way too often. It really only needs to do that if the previous
state of pendingEntries was FALSE and now it's true. I suppose we could
move the SetTimeout into the branches of the SELECT arms with some code of
the form
IF ~pendingEntries THEN {SetTimeout[...]; pendingEntries ← TRUE};
but then we need some more state. And it only happens once a second.
>>
--UNTIL ABORTED-- DO
ENABLE ABORTED => EXIT; --we're shutting down
WAIT xlate.event;
pendingEntries ← FALSE;
FOR e ← xlate.head, nextE UNTIL e = NIL DO
nextE ← e.nextLink; --copy out in case we delete entry
age ← [System.GetClockPulses[] - e.timeStamp];
SELECT e.status FROM
active, zombie =>
SELECT TRUE FROM
(age <= deactivatePulses) => NULL;
(e = xlate.me) => e.timeStamp ← System.GetClockPulses[];
(e = xlate.all) => e.timeStamp ← System.GetClockPulses[];
ENDCASE => {RemoveTranslate[xlate, e]; CommHeap.zone.FREE[@e]};
pending =>
BEGIN
SELECT TRUE FROM
(age < retryPulses) => NULL;
((e.tries ← e.tries + 1) > retryLimit) => e.status ← zombie;
ENDCASE => {SendRequest[]; e.timeStamp ← System.GetClockPulses[]};
pendingEntries ← TRUE;
END;
new =>
BEGIN
e.status ← pending;
SendRequest[];
e.timeStamp ← System.GetClockPulses[];
pendingEntries ← TRUE;
END;
ENDCASE => IF ArpaFlags.doDebug THEN ERROR;
ENDLOOP; --end of queue entries loop
IF ~pendingEntries THEN Process.DisableTimeout[@xlate.event]
ELSE Process.SetTimeout[@xlate.event, Process.SecondsToTicks[1]];
ENDLOOP;
FOR e ← xlate.head, nextE UNTIL e = NIL DO
nextE ← e.nextLink; CommHeap.zone.FREE[@e]; e ← nextE; ENDLOOP;
xlate.head ← xlate.me ← xlate.all ← NIL;
END; --Demon
ReceiveTranslate: PROC[b: Buffer.Buffer] =
BEGIN
OPEN context: LOOPHOLE[b.fo.context, ArpaRoutingTable.NetworkContext];
itsMe: BOOLEAN; --to suppress second call to AddrMatch
xlate: TranslaterHandle = context.protocol;
eb: EtherMAC.Encapsulation ← LOOPHOLE[b.linkLayer.blockPointer];
inPkt: LONG POINTER TO ArpBody ← LOOPHOLE[eb + wordsOfEncapsulation];
IF FindTranslate[xlate, inPkt.senderIpAddr] # NIL OR
(itsMe ← ArpaPortInternal.AddrMatch[xlate.hmsk, inPkt.targetIpAddr,
xlate.me.translatePair.arpaHost]) THEN
BEGIN
<<
The requester is probably going to talk to us or why else would he be
asking for our translation? So, since we have all the information, add
his translation to our table now. Then, when we have to talk back to
him, we won't fault.
>>
[] ← AddTranslateRecord[
xlate, [inPkt.senderEtherAddr, inPkt.senderIpAddr]];
IF ArpaFlags.doStats AND (inPkt.op = reply) THEN
ArpaStats.Incr[xlateRespRcvd];
IF itsMe AND (inPkt.op = request) THEN
BEGIN
--send the reply.
a: Buffer.Buffer;
IF ArpaFlags.doStats THEN ArpaStats.Incr[xlateReqRcvd];
--can't turn original around because dispatcher wants it back.
IF (a ← Buffer.GetBuffer[, pool, send, FALSE, bytesInArp]) # NIL THEN
BEGIN
ea: EtherMAC.Encapsulation ← LOOPHOLE[a.linkLayer.blockPointer];
body: LONG POINTER TO ArpBody ← LOOPHOLE[ea + wordsOfEncapsulation];
ea↑ ← [eb.ethernetSource, myEtherHost, arp];
a.highLayer ← [LOOPHOLE[body], 0, SIZE[ArpBody] * bpw];
a.fo.driver.length ← bytesOfEncapsulation + bytesInArp;
body↑ ← [etherHardware, arpa, etherAddrLen, ipAddrLen, reply,
xlate.me.translatePair.etherHost, xlate.me.translatePair.arpaHost,
inPkt.senderEtherAddr, inPkt.senderIpAddr];
a.linkLayer.stopIndexPlusOne ← bytesOfEncapsulation;
NARROW[b.fo.network, Device].sendRawBuffer[a];
IF ArpaFlags.doStats THEN ArpaStats.Incr[xlateRespSent];
END; --send the reply.
END;
END; --update or target.
END; --ReceiveTranslate
--called at start time.
myArpaAddr ← ArpaPortInternal.GetArpaAddr[];
END...
LOG
8-Feb-85 15:51:44 SMA Created file.
2-May-85 13:24:00 SMA Added cheating code to assign arpa host when started.
13-Jul-85 13:25:20 SMA Added stats.
22-Aug-85 10:34:40 SMA Added GetAddress for ArpaRouter.
14-Nov-85 8:55:15 SMA Speaks ARP.
4-Dec-85 10:44:36 SMA Get my address from ArpaAddressTranslation.
2-Jun-86 18:22:27 SMA Moved GetArpaAddr to ArpaRouterImpl for subnetting.
9-Mar-87 14:33:09 AOF Funston buffer managment
24-Mar-87 16:12:06 AOF Just some fine tuning.