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 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 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; 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 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; 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 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. pGVLocateImpl.mesa (Cedar) - Location of servers Copyright c 1985 by Xerox Corporation. All rights reserved. Andrew Birrell May 13, 1983 1:32 pm Mike Schroeder March 21, 1981 10:59 AM 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. caller promises that "i" is in range force socket number, because database may not have GV test-mode socket numbers terminate if we have enough addresses Note: EnumeratePupAddresses gives them closest first Top-level contacting R-Servers. Any method is valid! Try local broadcast, and try Name Lookup Server. find a registration server for given R-Name Κ Δ˜codešœ/™/Kšœ Οmœ1™š Ÿ œžœžœžœžœžœž˜7Kšœžœ˜—š Ÿ œžœžœžœž˜)Kšœžœ"˜4—šŸ œžœžœžœ˜>Kšžœž˜ Kšœ$™$Kšžœ$˜&šžœ/˜3K˜,—Kšœžœ˜#Kšžœžœ žœžœ˜#Kšœ žœ˜Kšžœ˜—šŸ œžœžœžœžœžœžœž˜IKšœDžœ˜L—š Ÿœžœžœžœžœ˜(Kš žœžœžœ žœžœ&žœ˜S—šŸœž œ˜Kšžœž˜ Kšœžœ˜Kšœ žœ ˜*Kšžœ žœžœ˜)šžœ žœ˜-Kšžœžœžœ˜&šžœžœ žœ˜+Kšžœžœ˜Kšžœ˜Kšžœ žœ(˜8Kšžœ(˜*šžœž˜ K˜2K˜K˜K˜$KšœN™NKšœ-˜-K˜K˜"K˜K˜Kšžœ˜——šž˜Kšœžœ ˜*—Kšžœ˜—Kšžœ˜Kšžœ˜—šŸœž œ˜Kšžœž˜ Kšžœ ˜šžœ%˜'Kšžœž˜ šžœž˜ šžœ ž˜˜ Kšžœ˜!Kšžœ$˜(——Kšžœžœ˜K˜Kšžœ˜——Kšžœ˜Kšžœ˜—Kšœ žœžœ ˜#Kšœ žœžœ ˜ K˜5Kšœ žœ˜Kšžœ ˜š žœžœžœžœž œ˜3Kšžœžœžœ˜&Kšžœ ˜šžœžœ ˜šžœž˜ K˜(Kšžœžœžœ˜-Kšžœ˜——Kšžœ˜—Kšžœ˜K˜Kšžœ ˜ Kšžœ ˜ Kšžœ˜K˜K˜—šŸœž œžœ˜8Kšž˜Kšœžœ ˜9šŸœž œžœžœ˜>Kšž˜Kšœ%™%Kšœ4™4Kšžœžœžœžœ˜0˜KšœR˜RKšœ  *œ˜4Kšœžœ˜—K˜Kšžœžœ˜ Kšžœ˜—Kšœf™fKšœžœ%˜/Kšœžœ˜Kšœ˜KšœK˜K˜=Kšœžœ˜%—Kšžœ˜K˜K˜—š Ÿ œžœžœ2žœžœ˜†Kšžœž˜ K˜5šžœ žœž˜Kšœ)˜)Kšœ˜˜Kšž˜Kšœ˜Kšœžœ˜'Kšœžœ˜Kšœ˜šžœ6žœ žœž˜NK˜K˜K˜4šžœž˜˜ Kšž˜˜šœ@˜@Kšœžœ˜%——˜K˜ Kšœžœ%žœ ˜?Kšœžœ˜—K˜Kšžœžœ˜6Kšžœ žœ˜Kšžœ˜——Kšžœžœ œ˜$—Kšžœ˜Kšžœ˜——Kšžœžœ˜Kšžœ˜K˜K˜—šŸœžœžœž œžœžœžœžœ"˜›Kšžœž˜ ˜2K˜K˜'—Kšœ˜Kšœ˜Kšžœžœ˜Kšžœ/˜3Kšžœ*˜.šžœž˜K˜ K˜šœ˜Kšž˜Kšžœ ˜+šžœ3˜5Kšžœ žœ!žœ˜:—Kšž˜Kšžœ˜Kšžœ˜Kšžœ˜——Kšžœžœ˜K˜!Kšžœ œ˜K˜—šŸœžœžœžœ˜7Kšžœ7˜>Kšž˜K˜&Kšžœ žœžœ˜%Kšžœ˜K˜—šŸ œžœžœžœžœžœžœžœ)˜™Kšž˜Kšœ+™+Kšœž œ  ˜!Kšœžœ˜Kšœžœ˜Kšžœž œžœ ˜Kšžœžœžœžœ˜#Kšžœžœžœ˜)Kšžœ˜KšžœX˜^Kšžœ ˜K˜K˜—š Ÿ œžœžœžœžœžœ˜CKšœžœžœ˜K˜—Kšžœ˜K˜K˜—…—*L