GVLocateImpl.mesa (Cedar) - Location of servers
Copyright © 1985 by Xerox Corporation. All rights reserved.
Andrew Birrell May 13, 1983 1:32 pm
Mike Schroeder March 21, 1981 10:59 AM
DIRECTORY
GVBasics USING [Connect, RName],
GVLocate USING [FoundServerInfo, FoundState],
GVNames USING [GetConnect, GetMembers, MemberInfo, NameType, RListHandle],
GVProtocol USING [GetSocket, IsLocal],
Process USING [MsecToTicks, SetTimeout ],
PupDefs USING [EnumeratePupAddresses, GetFreePupBuffer, GetHopsToNetwork, GetPupAddress, PupAddress, PupBuffer, PupNameTrouble, PupRouterSendThis, PupSocket, PupSocketDestroy, PupSocketID, PupSocketKick, PupSocketMake, ReturnFreePupBuffer, SetPupContentsWords, veryLongWait],
PupTypes USING [fillInSocketID, PupSocketID],
Rope USING [Cat, Equal, Fetch, Length, Substr];
GVLocateImpl:
CEDAR
MONITOR
IMPORTS GVNames, GVProtocol, Process, PupDefs, Rope
EXPORTS GVLocate = BEGIN
AddressInfo: TYPE = REF AddressInfoObject;
AddressInfoObject:
TYPE =
RECORD[
preSorted: BOOLEAN,
found: CARDINAL,
addresses: SEQUENCE possible: CARDINAL OF AddressRec];
AddressRec:
TYPE =
RECORD[
addr: PupDefs.PupAddress,
hops: HopCount,
reply: BOOLEAN];
HopCount: TYPE = [0..37777B];
ReplyInfo: TYPE = RECORD[ found: BOOLEAN, where: PupDefs.PupAddress ];
Prod:
PROCEDURE[ socket: PupDefs.PupSocket, addrInfo: AddressInfo, accept:
PROC[PupDefs.PupAddress]
RETURNS[
BOOLEAN] ]
RETURNS[ info: ReplyInfo ] =
TRUSTED BEGIN
This is complicated! The parameters are a table of candidate addresses, and a socket. The prodder process sends out "echoMe" pups to the addresses; the slurper process accepts "iAmEcho" replies, and marks the table. The original process reads the marks from the table, and calls the client's "accept" procedure to see if this address is ok. This satisfies various constraints about not hogging pup buffers. The "echoMe" packets are sent out to closer addresses first; they're not sent after the client has accepted an address. Everywhere, the Monitor is not locked while doing long waits.
from: PupDefs.PupAddress = socket.getLocalAddress[];
replyRecvd: BOOLEAN ← FALSE;-- "reply-waiting" flag
cond: CONDITION; -- notified when reply comes in
pleaseDie: BOOLEAN ← FALSE; -- for killing auxiliary processes
DeathWish:
ENTRY
PROC
RETURNS[
BOOLEAN] =
CHECKED
INLINE
{ RETURN[pleaseDie] };
KillSiblings:
ENTRY
PROC =
CHECKED
INLINE
{ pleaseDie ← TRUE; PupDefs.PupSocketKick[socket] };
NoteReply:
ENTRY
PROC[i:
CARDINAL, addr: PupDefs.PupAddress] =
CHECKED BEGIN
caller promises that "i" is in range
IF addrInfo.addresses[i].addr.host = 0
THEN { addrInfo.addresses[i].addr.host ← addr.host;
addrInfo.addresses[i].addr.net ← addr.net };
addrInfo.addresses[i].reply ← TRUE;
IF NOT replyRecvd THEN NOTIFY cond;
replyRecvd ← TRUE;
END;
TestReply:
ENTRY
PROC[i:
CARDINAL]
RETURNS[yes:
BOOLEAN] =
CHECKED
INLINE
{ yes ← addrInfo.addresses[i].reply; addrInfo.addresses[i].reply ← FALSE };
More:
ENTRY
PROC
RETURNS[yes:
BOOLEAN] =
CHECKED { IF NOT replyRecvd THEN WAIT cond; yes ← replyRecvd; replyRecvd ← FALSE };
SendProd:
PROCEDURE =
TRUSTED BEGIN
sent: CARDINAL ← 0;
lastHops: CARDINAL = 3; --sorting limit--
FOR wantedHops: CARDINAL IN [0..lastHops]
DO lastPass:
BOOLEAN = (wantedHops=lastHops);
FOR i: CARDINAL IN [0..addrInfo.found)
DO
IF DeathWish[]
OR sent >= addrInfo.found
THEN GOTO getUsOutOfHere;
IF addrInfo.preSorted
OR (lastPass AND addrInfo.addresses[i].hops>=wantedHops)
OR addrInfo.addresses[i].hops = wantedHops
THEN
BEGIN
b: PupDefs.PupBuffer = PupDefs.GetFreePupBuffer[];
b.source ← from;
b.pupType ← echoMe;
b.dest ← addrInfo.addresses[i].addr;
force socket number, because database may not have GV test-mode socket numbers
b.dest.socket ← GVProtocol.GetSocket[RSPoll];
b.pupWords[0] ← i;
PupDefs.SetPupContentsWords[b, 1];
PupDefs.PupRouterSendThis[b];
sent ← sent + 1;
END;
REPEAT
getUsOutOfHere => EXIT -- from outer loop!
ENDLOOP;
ENDLOOP;
END;
Slurp:
PROCEDURE =
TRUSTED BEGIN
UNTIL DeathWish[]
DO b: PupDefs.PupBuffer = socket.get[];
IF b # NIL
THEN
BEGIN
SELECT b.pupType
FROM
iAmEcho =>
IF b.pupWords[0] < addrInfo.found
THEN NoteReply[b.pupWords[0], b.source];
ENDCASE => NULL;
PupDefs.ReturnFreePupBuffer[b];
END;
ENDLOOP;
END;
prodder: PROCESS = FORK SendProd[];
slurper: PROCESS = FORK Slurp[];
Process.SetTimeout[@cond, Process.MsecToTicks[1500]];
info.found ← FALSE;
UNTIL info.found
DO
IF
NOT More[]
THEN
EXIT
-- time-out on "cond" --;
FOR i: CARDINAL IN [0..addrInfo.found)
UNTIL info.found
DO
IF TestReply[i]
THEN
BEGIN
info.where ← addrInfo.addresses[i].addr;
IF accept[info.where] THEN info.found ← TRUE;
END;
ENDLOOP;
ENDLOOP;
KillSiblings[];
JOIN prodder;
JOIN slurper;
END;
GetGVRegServer:
PROCEDURE
RETURNS[ info: AddressInfo ] =
BEGIN
addressesInGVRS: CARDINAL = 10; -- we take the 10 closest
Work:
PROCEDURE[addr: PupDefs.PupAddress]
RETURNS[
BOOLEAN ] =
BEGIN
terminate if we have enough addresses
Note: EnumeratePupAddresses gives them closest first
IF info.found = info.possible THEN RETURN[TRUE];
info.addresses[info.found] ← [
addr: [ net: addr.net, host: addr.host, socket: GVProtocol.GetSocket[RSEnquiry]],
hops: 0 -- ignored, because of "preSorted" flag --,
reply: FALSE ];
info.found ← info.found + 1;
RETURN[FALSE]
END;
Top-level contacting R-Servers. Any method is valid! Try local broadcast, and try Name Lookup Server.
info ← NEW[AddressInfoObject[addressesInGVRS]];
info.preSorted ← TRUE;
info.found ← 0;
[] ← Work[ [net:[0], host:[0], socket: GVProtocol.GetSocket[RSEnquiry] ] ];
[] ← PupDefs.EnumeratePupAddresses["GrapevineRServer", Work !
PupDefs.PupNameTrouble => CONTINUE ];
END;
GetGroupInfo:
PROC[ who: GVBasics.RName]
RETURNS[ state: GVLocate.FoundState, info: AddressInfo ←
NIL, local: GVBasics.RName ←
NIL ] =
TRUSTED BEGIN
mInfo: GVNames.MemberInfo = GVNames.GetMembers[who];
WITH m: mInfo
SELECT
FROM
notFound, individual => state ← notFound;
allDown => state ← allDown;
group =>
BEGIN
state ← found;
info ← NEW[AddressInfoObject[m.count]];
info.preSorted ← FALSE;
info.found ← 0;
FOR member: GVNames.RListHandle ← m.members, member.rest
UNTIL member =
NIL
DO
cInfo: GVNames.NameType;
connect: GVBasics.Connect;
[cInfo, connect] ← GVNames.GetConnect[member.first];
SELECT cInfo
FROM
individual =>
BEGIN
addr: PupDefs.PupAddress =
PupDefs.GetPupAddress[GVProtocol.GetSocket[RSEnquiry], connect !
PupDefs.PupNameTrouble => GOTO cant];
info.addresses[info.found] ← [
addr: addr,
hops: MIN[PupDefs.GetHopsToNetwork[addr.net], LAST[HopCount]],
reply: FALSE ];
info.found ← info.found + 1;
IF GVProtocol.IsLocal[addr] THEN local ← member.first;
EXITS cant => NULL;
END;
ENDCASE => NULL -- ignore others --;
ENDLOOP;
END;
ENDCASE => ERROR;
END;
FindNearestServer:
PUBLIC
SAFE
PROCEDURE[list: GVBasics.RName, accept:
PROC[PupDefs.PupAddress]
RETURNS[
BOOLEAN] ]
RETURNS[info: GVLocate.FoundServerInfo] =
TRUSTED BEGIN
socket: PupDefs.PupSocket = PupDefs.PupSocketMake[
local: PupTypes.fillInSocketID,
remote:, ticks: PupDefs.veryLongWait ];
addrInfo: AddressInfo;
state: GVLocate.FoundState;
IF list.Equal["gv.gv", FALSE]
THEN { state ← found; addrInfo ← GetGVRegServer[] }
ELSE [state, addrInfo, ] ← GetGroupInfo[list];
SELECT state
FROM
notFound => info ← [notFound[]];
allDown => info ← [allDown[]];
found =>
BEGIN
THROUGH [1..4] -- re-tries for lost packets
DO reply: ReplyInfo = Prod[socket, addrInfo, accept];
IF reply.found THEN { info ← [found[reply.where]]; EXIT }
REPEAT
FINISHED => info ← [allDown[]]
ENDLOOP;
END;
ENDCASE => ERROR;
PupDefs.PupSocketDestroy[socket];
END --FindNearestServer--;
FindLocalServer:
PUBLIC
SAFE
PROC[list: GVBasics.RName]
RETURNS[ state: GVLocate.FoundState, local: GVBasics.RName ] =
BEGIN
[state, , local] ← GetGroupInfo[list];
IF local = NIL THEN state ← notFound;
END;
FindRegServer:
PUBLIC
SAFE
PROC[ who: GVBasics.RName, accept:
PROC[PupDefs.PupAddress]
RETURNS[
BOOLEAN] ]
RETURNS[ foundInfo: GVLocate.FoundServerInfo ] =
BEGIN
find a registration server for given R-Name
sep: CHARACTER = '.; -- SN sep NA
length: INT = who.Length[];
i: INT;
FOR i DECREASING IN [0..length)
DO IF who.Fetch[i] = sep THEN EXIT;
REPEAT FINISHED => RETURN[ [notFound[]] ]
ENDLOOP;
RETURN[ FindNearestServer[Rope.Cat[who.Substr[start: i+1, len: length-i-1], ".gv"], accept] ];
END; --FindRegServer--
AcceptFirst:
PUBLIC
SAFE
PROC[PupDefs.PupAddress]
RETURNS[
BOOLEAN] =
{ RETURN[TRUE] };
END.