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 -- 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; 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. FGrapevineUser (Cedar) - Location of servers GVLocateImpl.mesa 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. Top-level contacting R-Servers. Any method is valid! Try local broadcast, and try Name Lookup Server. Ê µ˜Jšœ+™+Jšœ™Jšœ$™$Jšœ'™'J˜šÏk ˜ Jšœ œ˜ Jšœ œ˜-Jšœœ=˜JJšœ œ˜&Jšœœ˜)Jšœœ†˜“Jšœ œ˜-Jšœœ%˜/—J˜šœœ˜Jšœ,˜3Jšœ ˜J˜—Jš˜J˜Jšœ œœ˜*J˜šœœœ˜!Jšœ œ˜Jšœœ˜Jšœ œ œœ ˜6J˜—šœ œœ˜Jšœ˜J˜Jšœœ˜J˜—Jšœ œ˜J˜Jšœ œœ œ˜FJ˜š Ïnœ œ<œœœœ˜’Jšœ˜ JšœÌ™ÌJšœ4˜4Jšœ œœÏc˜6Jšœ œŸ"˜3Jšœ œœŸ%˜Aš ž œœœœœœ˜7Jšœœ˜—š ž œœœœ˜)Jšœœ"˜4—šž œœœœ˜>Jšœ˜ JšŸ*˜*Jšœ$˜&šœ/˜3J˜,—Jšœœ˜#Jšœœ œœ˜#Jšœ œ˜Jšœ˜—šž œœœœœœœ˜IJšœDœ˜L—š žœœœœœ˜(Jš œœœ œœ&œ˜S—šžœ œ˜Jšœ˜ Jšœœ˜Jšœ œŸ˜*Jšœ œœ˜)šœ œ˜-Jšœœœ˜&šœœ œ˜+Jšœœ˜Jšœ˜Jšœ œ(˜8Jšœ(˜*šœ˜ J˜2J˜J˜J˜$JšŸT˜TJšœ-˜-J˜J˜"J˜J˜Jšœ˜——š˜JšœœŸ˜-—Jšœ˜—Jšœ˜Jšœ˜—šžœ œ˜Jš ˜ Jšœ ˜šœ%˜'Jšœ˜ šœ˜ šœ ˜˜ Jšœ˜!Jšœ$˜(——Jšœœ˜J˜Jšœ˜——Jšœ˜Jšœ˜—Jšœ œœ ˜#Jšœ œœ ˜ J˜5Jšœ œ˜Jšœ ˜š œœœœŸœ˜3Jšœœœ˜&Jšœ ˜šœœ ˜šœ˜ J˜(Jšœœœ˜-Jšœ˜——Jšœ˜—Jšœ˜J˜Jšœ ˜ Jšœ ˜ Jšœ˜J˜J˜—šžœ œœ˜8Jš˜JšœœŸ˜<šžœ œœœ˜>Jš˜JšŸ+˜+JšŸ:˜:Jšœœœœ˜0˜JšœR˜RJšœ Ÿ*œ˜4Jšœœ˜—J˜Jšœœ˜ Jšœ˜—Jšœf™fJšœœ%˜/Jšœœ˜Jšœ˜JšœK˜K˜=Jšœœ˜%—Jšœ˜J˜J˜—š ž œœœ2œœ˜†Jšœ˜ J˜5šœ œ˜Jšœ)˜)Jšœ˜˜Jš˜Jšœ˜Jšœœ˜'Jšœœ˜Jšœ˜šœ6œ œ˜NJ˜J˜J˜4šœ˜˜ Jš˜˜šœ@˜@Jšœœ˜%——˜J˜ Jšœœ%œ ˜?Jšœœ˜—J˜Jšœœ˜6Jšœ œ˜Jšœ˜——JšœœŸœ˜$—Jšœ˜Jšœ˜——Jšœœ˜Jšœ˜J˜J˜—šžœœœœœœœ"˜›Jš ˜ ˜2J˜J˜'—Jšœ˜Jšœ˜Jšœœ˜Jšœ/˜3Jšœ*˜.šœ˜J˜ J˜šœ˜Jš˜JšœŸ˜.šœ3˜5Jšœ œ!œ˜:—Jš˜Jšœ˜Jšœ˜Jšœ˜——Jšœœ˜J˜!JšœŸœ˜J˜—šžœœœœ˜7Jšœ7˜>Jš˜J˜&Jšœ œœ˜%Jšœ˜J˜—šž œœœœœœœœ)˜™Jš˜JšŸ1˜1Jšœ œŸ˜$Jšœœ˜Jšœœ˜Jšœ œœ ˜Jšœœœœ˜#Jšœœœ˜)Jšœ˜JšœX˜^JšœŸ˜J˜J˜—š ž œœœœœœ˜CJšœœœ˜J˜—Jšœ˜J˜J˜—…—F*A