DIRECTORY Basics USING [bytesPerWord], BasicTime USING [GetClockPulses, MicrosecondsToPulses, Pulses], CommBuffer USING [Overhead], Driver USING [AllocBuffer, Buffer, FreeBuffer, GetNetworkChain, InsertReceiveProc, Network, RecvProc], DriverType USING [Encapsulation, ethernetOneBroadcastHost], NS USING [broadcastHost, GetThisHost, Host, unknownHost], Process USING [SecondsToTicks, SetPriority, SetTimeout, Ticks], Pup USING [allHosts, Host]; PupEthernetTranslation: CEDAR MONITOR LOCKS cH USING cH: Cache IMPORTS BasicTime, Driver, NS, Process EXPORTS CommBuffer ~ { BYTE: TYPE ~ [0..100H); bytesPerWord: NAT ~ Basics.bytesPerWord; Buffer: TYPE ~ Driver.Buffer; Network: TYPE ~ Driver.Network; Encapsulation: PUBLIC TYPE ~ DriverType.Encapsulation; -- exported to CommBuffer thisHost: NS.Host ~ NS.GetThisHost[]; Pulses: TYPE ~ BasicTime.Pulses; MSecsToPulses: PROC [n: LONG CARDINAL] RETURNS[Pulses] ~ INLINE { RETURN [BasicTime.MicrosecondsToPulses[1000*n]] }; PulsesSince: PROC [then: Pulses] RETURNS[Pulses] ~ INLINE { RETURN [BasicTime.GetClockPulses[] - then] }; TranslationType: TYPE ~ MACHINE DEPENDENT RECORD [a, b: BYTE]; requestType: TranslationType ~ [010H, 041H]; replyType: TranslationType ~ [00eH, 038H]; HostPair: TYPE ~ MACHINE DEPENDENT RECORD [ nsHost: NS.Host, pupHost: Pup.Host, filler: BYTE]; hostPairBytes: CARDINAL ~ bytesPerWord*SIZE[HostPair]; -- Should be BYTES[HostPair] TranslationPacketObject: TYPE ~ MACHINE DEPENDENT RECORD [ translationType: TranslationType, replier: HostPair, requestor: HostPair]; translationPacketBytes: CARDINAL ~ bytesPerWord*SIZE[TranslationPacketObject]; -- Should be BYTES[TranslationPacketObject]; Must be even! translationShortPacketBytes: CARDINAL ~ translationPacketBytes - hostPairBytes; -- CROCK: some old implementations send reply packets without the requestor field TranslationBuffer: TYPE ~ REF TranslationBufferObject; TranslationBufferObject: TYPE ~ MACHINE DEPENDENT RECORD [ ovh: CommBuffer.Overhead, translationType: TranslationType, replier: HostPair, requestor: HostPair]; numHashHeaders: CARDINAL ~ 256; HashIndex: TYPE ~ [0..numHashHeaders); Hash: PROC [pupHost: Pup.Host] RETURNS [HashIndex] ~ INLINE { RETURN [pupHost] }; Cache: TYPE ~ REF CacheObject; CacheObject: TYPE ~ MONITORED RECORD [ daemon: PROCESS, event: CONDITION, newPendingEntry: BOOL _ FALSE, sweepCheckTime: Pulses _ 0, sweepChecksUntilSweep: CARDINAL _ sweepChecksPerSweep, 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, referenced: BOOL, timeStamp: Pulses, tries: CARDINAL ]; pulsesPerSweepCheck: Pulses ~ MSecsToPulses[59500]; sweepCheckTimeout: Process.Ticks ~ Process.SecondsToTicks[60]; sweepChecksPerSweep: CARDINAL ~ 5; pulsesPerResend: Pulses ~ MSecsToPulses[1500]; resendTimeout: Process.Ticks _ Process.SecondsToTicks[1]; maxTries: CARDINAL ~ 8; noTranslation: INT _ 0; notQuick: INT _ 0; GetEncapsulation: PROC [network: Network, pupHost: Pup.Host] RETURNS [Encapsulation] ~ { cH: Cache ~ NARROW[network.pup.translation]; eH: CacheEntry _ NIL; hashIndex: HashIndex ~ Hash[pupHost]; BEGIN IF (eH _ cH.validEntries[hashIndex]) # NIL THEN { IF eH.hosts.pupHost = pupHost THEN GOTO Found; IF (eH _ eH.next) # NIL THEN { IF eH.hosts.pupHost = pupHost THEN GOTO Found; NULL; -- more checks would go here ... }; }; IF pupHost = Pup.allHosts THEN { eH _ cH.broadcastHostEntry; GOTO Found }; IF pupHost = network.pup.host THEN { eH _ cH.thisHostEntry; GOTO Found }; notQuick _ notQuick.SUCC; IF (eH _ GetCacheEntry[cH, hashIndex, pupHost]) # NIL THEN GOTO Found; GOTO NotFound; EXITS Found => { eH.referenced _ TRUE; TRUSTED { RETURN[ [ethernet[ethernetDest~eH.hosts.nsHost, ethernetSource~thisHost, ethernetType~oldPup]] ] } }; NotFound => { noTranslation _ noTranslation.SUCC; TRUSTED { RETURN[ [ethernet[ethernetDest~NS.unknownHost, ethernetSource~thisHost, ethernetType~translationFailed]] ] } }; END; }; GetCacheEntry: ENTRY PROC [cH: Cache, hashIndex: HashIndex, pupHost: Pup.Host] RETURNS [CacheEntry] ~ { eH, prevH: CacheEntry; eH _ cH.validEntries[hashIndex]; prevH _ NIL; WHILE eH # NIL DO IF eH.hosts.pupHost = pupHost THEN { IF prevH # NIL THEN { prevH.next _ eH.next; eH.next _ cH.validEntries[hashIndex]; cH.validEntries[hashIndex] _ eH }; RETURN[eH] }; prevH _ eH; eH _ eH.next ENDLOOP; FOR eH _ cH.pendingEntries, eH.next WHILE eH # NIL DO IF eH.hosts.pupHost = pupHost THEN RETURN[NIL]; ENDLOOP; TRUSTED { cH.pendingEntries _ NEW[ CacheEntryObject _ [next~cH.pendingEntries, hosts~[nsHost~NS.unknownHost, pupHost~pupHost, filler~], referenced~TRUE, timeStamp~BasicTime.GetClockPulses[], tries~0] ] }; cH.newPendingEntry _ TRUE; NOTIFY cH.event; RETURN[NIL] }; MakeRequest: PROC [cH: Cache, pupHost: Pup.Host, sendTo: NS.Host _ NS.broadcastHost] RETURNS [b: Buffer] ~ { bH: TranslationBuffer; b _ Driver.AllocBuffer[]; TRUSTED { bH _ LOOPHOLE[b] }; bH.translationType _ requestType; bH.replier _ [nsHost~NS.unknownHost, pupHost~pupHost, filler~0]; bH.requestor _ cH.thisHostEntry.hosts; TRUSTED { bH.ovh.encap _ Encapsulation[ethernet[ethernetDest~sendTo, ethernetSource~thisHost, ethernetType~oldPupTranslation]] }; }; ConvertToReply: PROC [cH: Cache, bH: TranslationBuffer] ~ { bH.translationType _ replyType; bH.replier _ cH.thisHostEntry.hosts; TRUSTED { bH.ovh.encap _ Encapsulation[ethernet[ethernetDest~bH.requestor.nsHost, ethernetSource~thisHost, ethernetType~oldPupTranslation]] }; }; AddTranslation: ENTRY PROC [cH: Cache, hosts: HostPair] ~ { eH, prevH: CacheEntry; i: HashIndex ~ Hash[hosts.pupHost]; eH _ cH.pendingEntries; prevH _ NIL; WHILE eH # NIL DO IF eH.hosts.pupHost = hosts.pupHost 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.pupHost = hosts.pupHost 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 cH.validEntries[i] _ NEW[ CacheEntryObject _ [next~cH.validEntries[i], hosts~hosts, referenced~TRUE, timeStamp~BasicTime.GetClockPulses[], tries~0] ] ELSE { eH.next _ cH.validEntries[i]; cH.validEntries[i] _ eH }; }; requestsReceived: INT _ 0; repliesReceived: INT _ 0; tooShort: INT _ 0; badProtocol: INT _ 0; RecvTranslation: Driver.RecvProc ~ { cH: Cache ~ NARROW[network.pup.translation]; bH: TranslationBuffer; IF bytes < translationShortPacketBytes THEN { tooShort _ tooShort.SUCC; RETURN [buffer] }; TRUSTED { bH _ LOOPHOLE[buffer] }; SELECT TRUE FROM bH.translationType = requestType => { IF bytes < translationPacketBytes THEN { tooShort _ tooShort.SUCC; RETURN [buffer] }; IF bH.replier.pupHost = network.pup.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, sweepCheckTimeout] }; WAIT cH.event }; prevH _ NIL; eH _ cH.pendingEntries; WHILE eH # NIL DO IF PulsesSince[eH.timeStamp] >= pulsesPerResend THEN { IF eH.tries >= maxTries THEN { eH _ eH.next; IF prevH = NIL THEN cH.pendingEntries _ eH ELSE prevH.next _ eH; LOOP }; eH.tries _ eH.tries + 1; eH.timeStamp _ BasicTime.GetClockPulses[]; { buffer: Buffer ~ MakeRequest[cH, eH.hosts.pupHost]; InternalEnqueueForSending[cH, buffer] }; }; prevH _ eH; eH _ eH.next; ENDLOOP; cH.newPendingEntry _ FALSE; IF PulsesSince[cH.sweepCheckTime] >= pulsesPerSweepCheck THEN { cH.sweepCheckTime _ BasicTime.GetClockPulses[]; IF cH.sweepChecksUntilSweep = 0 THEN { FOR i: HashIndex IN [0..numHashHeaders) DO eH _ cH.validEntries[i]; prevH _ NIL; WHILE eH # NIL DO IF eH.referenced THEN { eH.referenced _ FALSE; prevH _ eH; eH _ eH.next } ELSE { eH _ eH.next; IF prevH = NIL THEN cH.validEntries[i] _ eH ELSE prevH.next _ eH }; ENDLOOP; ENDLOOP; cH.sweepChecksUntilSweep _ sweepChecksPerSweep; } ELSE { cH.sweepChecksUntilSweep _ cH.sweepChecksUntilSweep - 1; }; }; }; Daemon: PROC [network: Network] ~ { cH: Cache ~ NARROW[ network.pup.translation ]; buffer: Buffer; Process.SetPriority[3]; -- ??? DO WaitAndScanCache[cH]; WHILE (buffer _ DequeueForSending[cH]) # NIL DO network.pup.sendTranslate[network, buffer, translationPacketBytes]; Driver.FreeBuffer[buffer]; ENDLOOP; ENDLOOP; }; Init: PROC = { cH: Cache; FOR network: Network _ Driver.GetNetworkChain[], network.next UNTIL network = NIL DO IF network.type # ethernet THEN LOOP; cH _ NEW[ CacheObject _ [] ]; cH.broadcastHostEntry _ NEW[ CacheEntryObject _ [hosts~[nsHost~NS.broadcastHost, pupHost~DriverType.ethernetOneBroadcastHost, filler~], referenced~, timeStamp~, tries~] ]; cH.thisHostEntry _ NEW[ CacheEntryObject _ [hosts~[nsHost~thisHost, pupHost~network.pup.host, filler~], referenced~, timeStamp~, tries~] ]; network.pup.translation _ cH; network.pup.getEncapsulation _ GetEncapsulation; Driver.InsertReceiveProc[network~network, type~pupTranslate, proc~RecvTranslation]; cH.daemon _ FORK Daemon[network]; ENDLOOP; }; TryHost: PROC [pupHost: Pup.Host] ~ { FOR network: Network _ Driver.GetNetworkChain[], network.next UNTIL network = NIL DO IF network.type = ethernet THEN { [] _ GetEncapsulation[network, pupHost]; EXIT }; ENDLOOP; }; Init[]; }. ’PupEthernetTranslation.mesa Copyright c 1986 by Xerox Corporation. All rights reserved. Demers, February 5, 1986 5:04:32 pm PST Hal Murray, April 3, 1986 7:47:02 pm PST Adapted from NSEthernetOneTranslation.mesa which in turn was Very freely adapted from translation code in: Cedar6.0>OISCP>EthernetOneDriver.mesa Birrell on: 9-Oct-81 16:43:32 BLyon on: March 13, 1981 10:47 PM Levin, August 9, 1983 9:28 am Russ Atkinson (RRA) February 19, 1985 7:44:43 pm PST Time Translation Request / Reply Packets Translation Entry Cache For the Pup world, the number of hash headers has been set to the size of the Pup Host space. 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 [pupHost: Pup.Host] RETURNS [HashIndex] ~ INLINE { RETURN [ pupHost MOD numHashHeaders ] }; Timeouts Encapsulating Pup 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. Building Request / Reply Packets Allocate a buffer, build a request packet in it, and return it. The sendTo parameter is the NS 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. 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] CROCK: the following test should be "< translationPacketBytes", but some old implementations send reply packets without the requestor field. Eventually, when the old implementations go away, fix it by moving the other CROCK (below) up to this position. CROCK: the following test should be moved up to replace the previous CROCK. Daemon Process Delete the entry. Do a sweep check ... Do a sweep ... Delete the entry. Initialization Install a cache (and start a daemon) for each ethernet on the chain. Hack for debugging use from the Interpreter: Κ α˜codešœ™Kšœ Οmœ1™K˜Kšœ,˜,Kšœ*˜*K˜š œ žœžœž œžœ˜+Kšœžœ˜K˜Kšœžœ˜K˜—šœžœžœ  ˜SK˜—šœ žœž œžœ˜:Kšœ!˜!K˜K˜K˜—Kšœžœžœ :˜‰šœžœ+ Q˜‘K˜—Kšœžœžœ˜6š œžœžœž œžœ˜:K˜Kšœ!˜!K˜K˜K˜——™K™ΎK™Kšœžœ˜Kšœ žœ˜&K˜š‘œžœžœžœ˜=Kšžœ ˜—K˜š‘œžœžœžœ™=Kšžœ žœ™(K™—Kšœžœžœ ˜šœ žœž œžœ˜&Kšœžœ˜Kšœž œ˜Kšœžœžœ˜K˜Kšœž œ˜6K˜Kšœ˜Kšœ˜Kšœ˜Kšœžœ žœ ˜-K˜—K˜Kšœ žœžœ˜(šœžœžœ˜!Kšœ˜Kšœ˜Kšœ žœ˜Kšœ˜Kšœž˜Kšœ˜——™K˜3Kšœ>˜>Kšœžœ˜"K˜Kšœ.˜.Kšœ9˜9K˜Kšœ žœ˜K˜—™™ Kšœžœ˜Kšœ žœ˜—K˜š‘œžœ'žœ˜XKšœ žœ˜,Kšœžœ˜Kšœ%˜%K˜šž˜K™<šžœ%žœžœ˜1Kšžœžœžœ˜.šžœžœžœ˜Kšžœžœžœ˜.Kšžœ !˜'K˜—K˜—Kšžœžœžœ ˜JKšžœžœžœ ˜IKšœžœ˜Kšžœ0žœžœžœ˜FKšžœ ˜K˜šž˜šœ ˜ Kšœžœ˜Kšžœžœ\˜lK˜—šœ ˜ Kšœžœ˜#KšžœžœžœK˜vK˜——Kšžœ˜—K˜K˜—K˜š‘ œžœžœ6žœ˜gK™–K˜Kšœ˜K˜Kšœ*žœ˜.šžœžœž˜šžœžœ˜$K™šžœ žœžœ˜K˜Kšœ%˜%Kšœ"˜"—Kšžœ˜ —K˜Kšž˜—K˜šžœ!žœžœž˜5Kšžœžœžœžœ˜/Kšžœ˜—K˜Kšžœžœržœ5˜ΜKšœžœžœ ˜,Kšžœžœ˜K˜——™ š‘ œžœ(žœžœ˜lK™?K™K˜Kšœ˜Kšžœžœ˜Kšœ!˜!Kšœžœ)˜@K˜&Kšžœz˜K˜—K˜š‘œžœ'˜;K™>K™vKšœ˜K˜$Kšžœ‡˜Ž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šžœžœGžœ2˜šKšžœ<˜@—K˜K˜—K˜™Kšœžœ˜Kšœžœ˜Kšœ žœ˜Kšœ žœ˜—K˜š‘œ˜ Kšœ*žœžœ ™?Kšœ˜Kšœ žœ˜,K˜K˜šœI ΄™ύšžœ%žœ˜-Kšœžœ˜Kšžœ ˜——K˜Kšžœžœ ˜"šžœžœž˜šœ%˜%™Kšžœ žœ˜(Kšœžœ˜Kšžœ ˜——šžœ'žœ˜/Kšœ$žœ˜)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šžœ4˜8—Kšžœ ˜—K˜Kšœžœ˜%šžœžœž˜šžœ.žœ˜6šžœžœž˜K™K˜ Kšžœ žœžœžœ˜@Kšžœ˜—K˜Kšœ*˜*šœ5˜5Kšœ(˜(—K˜—K˜Kšžœ˜—Kšœžœ˜K˜šžœ7žœ˜?K™Kšœ/˜/šžœ˜šžœ˜K™šžœžœž˜*Kšœ"žœ˜&šžœžœž˜šžœ˜šžœ˜Kšœžœ˜K˜—šžœ˜K™K˜ Kšžœ žœžœžœ˜C——Kšžœ˜—Kšžœ˜—Kšœ/˜/K˜—šžœ˜Kšœ8˜8K˜——K˜—K˜Kšœ˜K˜K˜—š‘œžœ˜#Kšœ žœ˜.K˜Kšœ ˜šž˜K˜šžœ$žœž˜/KšœC˜CKšœ˜Kšžœ˜—Kšžœ˜—Kšœ˜K˜——™š‘œžœ˜K™DK˜ K˜šžœ;žœ žœž˜TKšžœžœžœ˜%Kšœžœ˜Kšœžœ$žœj˜«Kšœžœu˜‹K˜Kšœ0˜0KšœS˜SKšœ žœ˜!Kšžœ˜—K˜K˜—K˜—K™,K˜š‘œžœ˜%šžœ;žœ žœž˜Tšžœžœ˜!Kšœ*žœ˜1—Kšžœ˜—K˜K˜—K˜K˜Kšœ˜—J˜—…—)v@ι