DIRECTORY Arpa USING [Address], ArpaTranslation USING [DetermineAddressAndSubnetMaskForInterface, GetNet, GetSubnetMask, GetTranslationTable, PutTranslationTable], Basics USING [HWORD, 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 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 ~ [255, 255, 255, 255]; 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] }; 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, requestor: HostPair, replier: 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, requestor: HostPair, replier: HostPair]; numHashHeaders: CARDINAL ~ 256; HashIndex: TYPE ~ [0..numHashHeaders); Hash: PROC [arpaHost: Arpa.Address] RETURNS [HashIndex] ~ INLINE { RETURN [ LOOPHOLE[arpaHost, CARD] MOD numHashHeaders ] }; Cache: TYPE ~ REF CacheObject; CacheObject: TYPE ~ MONITORED RECORD [ daemon: PROCESS, event: CONDITION, newPendingEntry: BOOL _ FALSE, 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] }; 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; noTranslation: INT _ 0; notQuick: INT _ 0; GetEncapsulation: PROC [network: Network, arpaHost: Arpa.Address] RETURNS [Encapsulation] ~ { cH: Cache _ NARROW[ArpaTranslation.GetTranslationTable[network]]; eH: CacheEntry _ NIL; hashIndex: HashIndex ~ Hash[arpaHost]; broadcastHost: Arpa.Address _ LOOPHOLE[Basics.DoubleOr[LOOPHOLE[ArpaTranslation.GetNet[network]], Basics.DoubleNot[LOOPHOLE[ArpaTranslation.GetSubnetMask[network]]]]]; BEGIN 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 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] ~ { eH, prevH: CacheEntry; eH _ cH.validEntries[hashIndex]; prevH _ NIL; WHILE eH # NIL DO IF eH.hosts.arpaHost = arpaHost THEN { IF UpToDate[eH] THEN { IF prevH # NIL THEN { prevH.next _ eH.next; eH.next _ cH.validEntries[hashIndex]; cH.validEntries[hashIndex] _ eH }; RETURN[eH] } ELSE { 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; 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] }; MakeRequest: PROC [cH: Cache, arpaHost: Arpa.Address, sendTo: XNS.Host _ XNS.broadcastHost] RETURNS [b: Buffer] ~ { 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.replier _ [nsHost~XNS.unknownHost, arpaHost~arpaHost]; bH.requestor _ cH.thisHostEntry.hosts; TRUSTED { bH.ovh.encap _ Encapsulation[ethernet[ethernetDest~sendTo, ethernetSource~thisHost, ethernetType~arp]] }; }; ConvertToReply: PROC [cH: Cache, bH: TranslationBuffer] ~ { bH.hardwareType _ ethernet; bH.protocolType _ ipType; bH.hardwareAddressLength _ ethernetAddressLength; bH.protocolAddressLength _ ipAddressLength; bH.translationType _ replyType; bH.replier _ cH.thisHostEntry.hosts; TRUSTED { bH.ovh.encap _ Encapsulation[ethernet[ethernetDest~bH.requestor.nsHost, ethernetSource~thisHost, ethernetType~arp]] }; }; AddTranslation: ENTRY PROC [cH: Cache, hosts: HostPair] ~ { eH, prevH: CacheEntry; i: HashIndex ~ Hash[hosts.arpaHost]; 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 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 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; }; requestsReceived: INT _ 0; repliesReceived: INT _ 0; tooShort: INT _ 0; badProtocol: INT _ 0; RecvTranslation: CommDriver.RecvProc ~ { 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.replier.arpaHost = network.arpa.host THEN { requestsReceived _ requestsReceived.SUCC; AddTranslation[cH, bH.requestor]; ConvertToReply[cH, bH]; EnqueueForSending[cH, buffer]; buffer _ NIL; }; }; bH.translationType = replyType => { repliesReceived _ repliesReceived.SUCC; AddTranslation[cH, bH.replier]; }; ENDCASE => { badProtocol _ badProtocol.SUCC }; RETURN[buffer]; }; 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] }; 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 { eH _ eH.next; IF prevH = NIL THEN cH.pendingEntries _ eH ELSE prevH.next _ eH; LOOP }; { 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 THEN { 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; }; Init: PROC = { 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[]; }. ΒArpaEthernetTranslation.mesa Copyright Σ 1987 by Xerox Corporation. All rights reserved. John Larson, August 20, 1987 4:07:19 pm PDT Adapted from XNSEthernetOneTranslation.mesa. See the Address Resolution Protocol (ARP) spec RFC826.TXT for more details. Time Ethernet ARP Request / Reply Packets 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. Hash: PROC [arpaHost: Arpa.Address] RETURNS [HashIndex] ~ INLINE { RETURN [arpaHost] }; Timeouts Encapsulating Arpa Packets Statistics Quick check of first couple of entries without acquiring ML. 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. Move entry to head of list. Entry needs to be refreshed  move it to pending list. Search for a pending entry. Building Request / Reply Packets 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. 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 ... Processing Received Translation Packets Look for a pending entry. If no pending entry, look for a valid one. If existing entry is incorrect, drop it on the floor ... Receive Statistics [network: Network, buffer: Buffer, bytes: NAT] RETURNS [Buffer] Daemon Process Delete the entry. Send the entry Do a sweep ... Initialization Install a cache (and start a daemon) for each ethernet on the chain. Κ΅˜codešœ™Kšœ<™—Kšœ˜—K˜Kšœœ<œe˜ΕKšœœœ ˜,Kšœœ˜K˜——™ š ž œœ-œœœ˜sK™?K™€K˜Kšœ˜Kšœœ˜Kšœ˜Kšœ˜Kšœ1˜1Kšœ+˜+Kšœ!˜!Kšœœ!˜9K˜&Kšœl˜sK˜—K˜šžœœ'˜;K™>K™vK™K™,Kšœ˜Kšœ˜Kšœ1˜1Kšœ+˜+K˜Kšœ˜K˜$Kšœy˜€K˜K˜——™'šžœœœ!˜;K˜Kšœ$˜$K˜K™Kšœ!œ˜%šœœ˜šœ&œ˜,Kšœ œœœ˜JK˜Kšœ˜—K˜Kšœ˜—K˜K™*šœœœ˜Kšœ"œ˜&šœœ˜šœ$œ˜,Kšœ œœœ˜K™8Kšœ œœ˜0—Kšœ˜—K˜Kšœ˜—K˜—K˜šœ˜ KšœœE˜R—Kšœ˜Kšœ˜Kšœ˜K˜K˜—K˜™Kšœœ˜Kšœœ˜Kšœ œ˜Kšœ œ˜—K˜šžœ˜$Kšœ*œœ ™?Kšœ˜Kšœ œ/˜AK˜K˜—™šœ œ˜(Kšœœ˜Kšœ ˜—K˜Kšœœ ˜"šœœ˜šœ%˜%šœ)œ˜1Kšœ$œ˜)Kšœ!˜!K˜K˜Kšœ œ˜ K˜—Kšœ˜—šœ#˜#Kšœ"œ˜'Kšœ˜K˜—šœ˜ Kšœœ˜!——Kšœ ˜K˜K˜——™šžœ œ˜8Kšœœœœ˜HKšœ˜Kšœ ˜Kšœ ˜K˜—šžœœ˜CKšœœœœ˜HKšœ˜Kšœ ˜Kšœ ˜K˜—šžœœœ œ˜AKšœœœœ˜'Kš œœœœœ˜CK˜K˜—š žœœœ œœœ˜MKšœœ˜—K˜K˜šžœœœ˜,K˜K˜šœœœœ˜Ašœœ˜$Kšœ-˜1Kšœ/˜3—Kšœ ˜—K˜Kšœœ˜%šœœ˜šœ!œ˜)šœœ˜K™K˜ Kšœ œœœ˜@Kšœ˜—šœ˜KšŸ™Kšœ œœ#œœœœœ˜ŽKšœ>˜>Kšœ&˜&Kšœ"˜"Kšœ=˜=K˜—K˜—K˜Kšœ˜—Kšœœ˜K˜šœ-œ˜5K™šœœ˜*šœ"œœ˜6Kšœœ#˜