DIRECTORY
Basics USING [HWORD],
BasicTime USING [GetClockPulses, MicrosecondsToPulses, Pulses],
CommBuffer USING [Overhead],
CommDriver USING [AllocBuffer, Buffer, FreeBuffer, GetNetworkChain, InsertReceiveProc, Network, RecvProc],
CommDriverType USING [Encapsulation, ethernetOneBroadcastHost],
Process USING [MsecToTicks, priorityForeground, SecondsToTicks, SetPriority, SetTimeout, Ticks],
Pup USING [allHosts, Host],
XNS USING [broadcastHost, GetThisHost, Host, unknownHost];

PupEthernetTranslation: CEDAR MONITOR
LOCKS cH USING cH: Cache
IMPORTS 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[];
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] };


TranslationType: TYPE ~ Basics.HWORD;

requestType: TranslationType ~ [010H, 041H];
replyType: TranslationType ~ [00eH, 038H];

HostPair: TYPE ~ MACHINE DEPENDENT RECORD [
nsHost: XNS.Host,
pupHost: Pup.Host,
filler: BYTE];

hostPairBytes: CARDINAL ~ BYTES[HostPair];

TranslationPacketObject: TYPE ~ MACHINE DEPENDENT RECORD [
translationType: TranslationType,
replier: HostPair,
requestor: HostPair];

translationPacketBytes: CARDINAL ~ 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,
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, 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) AND UpToDate[eH] THEN GOTO Found;
IF (eH _ eH.next) # NIL THEN {
IF (eH.hosts.pupHost = pupHost) AND UpToDate[eH] 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 => {
TRUSTED { RETURN[ [ethernet[ethernetDest~eH.hosts.nsHost, ethernetSource~thisHost, ethernetType~oldPup]] ] }
};
NotFound => {
noTranslation _ noTranslation.SUCC;
TRUSTED { RETURN[ [ethernet[ethernetDest~XNS.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 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.pupHost = pupHost 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, pupHost~pupHost, filler~], whenToSend~BasicTime.GetClockPulses[], timeToLive~sendsToLive] ] };
cH.newPendingEntry _ TRUE;  NOTIFY cH.event;
RETURN[NIL] };

MakeRequest: PROC [cH: Cache, pupHost: Pup.Host, sendTo: XNS.Host _ XNS.broadcastHost] RETURNS [b: Buffer] ~ {
bH: TranslationBuffer;
b _ CommDriver.AllocBuffer[];
TRUSTED { bH _ LOOPHOLE[b] };
bH.translationType _ requestType;
bH.replier _ [nsHost~XNS.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 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[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, 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.pupHost, 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[ network.pup.translation ];
buffer: Buffer;
Process.SetPriority[Process.priorityForeground];
DO
WaitAndScanCache[cH];
WHILE (buffer _ DequeueForSending[cH]) # NIL DO
network.pup.sendTranslate[network, buffer, translationPacketBytes];
CommDriver.FreeBuffer[buffer];
ENDLOOP;
ENDLOOP;
};

Init: PROC = {
cH: Cache;

FOR network: Network _ CommDriver.GetNetworkChain[], network.next UNTIL network = NIL DO
IF network.type # ethernet THEN LOOP;
cH _ NEW[ CacheObject _ [sweepTime~BasicTime.GetClockPulses[]] ];
cH.broadcastHostEntry _ NEW[ CacheEntryObject _ [hosts~[nsHost~XNS.broadcastHost, pupHost~CommDriverType.ethernetOneBroadcastHost, filler~], whenToSend~, timeToLive~] ];
cH.thisHostEntry _ NEW[ CacheEntryObject _ [hosts~[nsHost~thisHost, pupHost~network.pup.host, filler~], whenToSend~, timeToLive~] ];
network.pup.translation _ cH;
network.pup.getEncapsulation _ GetEncapsulation;
CommDriver.InsertReceiveProc[network~network, type~pupTranslate, proc~RecvTranslation];
cH.daemon _ FORK Daemon[network];
ENDLOOP;
};

Init[];

}.


	ΠPupEthernetTranslation.mesa
Copyright Σ 1986, 1987 by Xerox Corporation.  All rights reserved.
Demers, July 24, 1987 2:33:55 pm PDT
Hal Murray, May 29, 1986 2:39:13 am PDT
Doug Wyatt, January 16, 1987 3:37:22 pm PST

Adapted from XNSEthernetOneTranslation.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.
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.
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.
Send the entry
Do a sweep ...
Initialization
Install a cache (and start a daemon) for each ethernet on the chain.
Κ
Α˜
codeš
œ™Kš
œB™BK™$K™'K™+K™—š
œ+™+K™K™K™—š
œS™SKš
œ™Kš
œ"™"Kš
œ™J™4—J˜š
Οk	˜	Jšœœœ˜Jšœ
œ0˜?Jšœœ˜KšœœZ˜jKšœœ+˜?Kš
œ`˜`Kšœœ˜Kšœ
œ1˜:K˜—šΠblœœ
˜%Kšœœ
˜Kšœ!˜+Kšœ˜Kš
œ˜K˜Kšœœ˜!Kšœ	œ˜#K˜Kšœœ
œ!Οc˜TK˜Kšœ
œœ˜'
head™Kšœœ˜ K˜š
Οn
œœœœœ˜9Kšœ,˜2—K˜š œœœœ˜<Kšœ'˜-—K˜K˜—™#Kšœœ
œ
˜%K˜Kš
œ,˜,Kš
œ*˜*K˜š	œ
œœ
	œ
œ˜+Kšœœ˜K˜Kšœœ˜K˜—šœœœ˜*K˜—š	œœœ
	œ
œ˜:Kš
œ!˜!K˜K˜K˜—KšœœœŸ˜Sšœœ+ŸQ˜‘
K˜—Kšœœœ˜6š	œœœ
	œ
œ˜:K˜Kš
œ!˜!K˜K˜K˜——™K™ΎK™Kšœœ˜Kšœœ˜&K˜š œœœœ˜=Kšœ
˜—K˜š œœœœ™=Kšœœ™(K™—Kšœœœ
˜šœ
œ	œ
œ˜&Kšœœ
˜Kšœ	œ
˜Kšœœœ
˜K˜K˜Kš
œ˜Kš
œ˜Kš
œ˜Kšœœœ
˜-K˜—K˜Kšœœœ˜(šœœœ˜!Kš
œ˜Kš
œ˜J˜Kšœ˜Kš
œ˜K˜—š œœœœ
˜.Kšœœœ˜(——™K˜.Kš
œ9˜9Kšœœ˜K˜Kš
œ-˜-Kš
œ8˜8Kšœ
œ˜K˜—™™
Kšœœ˜Kšœ
œ˜—K˜š œœ'œ˜XKšœœ˜,Kšœœ
˜Kš
œ%˜%K˜š
˜K™<šœ%œ
œ˜1Kšœœœ
œ˜Ašœœ
œ˜Kšœœœ
œ˜AKšœŸ!˜'K˜—K˜—Kšœœœ	˜JKšœœœ	˜IKšœœ
˜Kšœ0œ
œ
œ˜FKšœ
˜K˜š
˜š
œ
˜
Kšœœ\˜lK˜—š
œ
˜
Kšœœ
˜#KšœœœK˜wK˜——Kšœ
˜—K˜K˜—K˜š 
œœ
œ6œ˜gK™–
K˜Kš
œ˜K˜Kšœ*œ
˜.šœœ
˜šœœ˜$šœ
˜šœ˜K™šœ	œ
œ˜K˜Kš
œ%˜%Kš
œ"˜"—Kšœ˜—šœ˜K™6šœ	˜Kšœ˜Kšœ&˜*—K˜Kš
œ+˜+K˜K˜Kšœœœ
˜,Kšœ˜
——K˜—K˜Kš
˜—K˜K™šœ!œœ
˜5šœ˜"Kšœ
œœ
œœ
œ˜>—Kšœ
˜—K˜Kšœœ<œl˜Μ
Kšœœœ
˜,Kšœ
œ˜K˜——™ š
 œœ(œœœ˜nK™?K™€
K˜Kš
œ˜Kšœœ˜Kš
œ!˜!Kšœœ)˜AK˜&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šœœE˜R—Kš
œ˜Kš
œ˜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šœ/˜3—Kšœ˜—K˜Kšœœ˜%šœœ
˜šœ!œ˜)šœœ

˜K™K˜
Kšœ	œ
œœ˜@Kšœ˜—š
œ
˜
Kš
Ÿ™Kšœ
œœ#œœœœ
œ˜Ž
Kš
œ=˜=Kš
œ&˜&Kš
œ"˜"Kš
œ=˜=K˜—K˜—K˜Kšœ
˜—Kšœœ
˜K˜šœ-œ˜5K™šœœ˜*šœ"œœ
˜6Kšœœ#˜<Kšœ
˜—Kšœ
˜—Kš
œ*˜*K˜—K˜Kš
œ˜K˜K˜—š œœ˜#Kšœœ˜.K˜Kš
œ0˜0š
˜K˜šœ$œ
˜/Kš
œC˜CKš
œ˜Kšœ
˜—Kšœ
˜—Kš
œ˜K˜——™š œœ˜K™DK˜
K˜šœ?œœ
˜XKšœœ
œ
˜%Kšœœ9˜AKšœœ$œg˜©
Kšœœn˜„
K˜Kš
œ0˜0Kš
œW˜WKšœœ˜!Kšœ
˜—K˜K˜——K˜K˜Kš
œ˜—J˜J˜—…—)@«