<<>> <> <> <> <> <<>> <<>> DIRECTORY Basics, BasicTime, Commander, CommanderOps, Convert, Rope, RedBlackTree, PFS, PFSNames, PriorityQueue, Process, Real, SymTab, IO, UnixSpawnTCP; BackupSchedulerImpl: CEDAR MONITOR IMPORTS Basics, BasicTime, Commander, CommanderOps, Convert, Rope, RedBlackTree, Real, PFS, PFSNames, PriorityQueue, Process, SymTab, IO, UnixSpawnTCP ~ BEGIN ROPE: TYPE ~ Rope.ROPE; STREAM: TYPE ~ IO.STREAM; GMT: TYPE ~ BasicTime.GMT; nullGMT: GMT ~ BasicTime.nullGMT; PQ: TYPE ~ PriorityQueue.Ref; Tree: TYPE ~ RedBlackTree.Table; Day: TYPE ~ {Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday}; Days: ARRAY Day OF ROPE ~ ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]; NextDay: PROC [d: Day] RETURNS [Day] ~ { RETURN [IF d=Sunday THEN Monday ELSE d.SUCC] }; PrevDay: PROC [d: Day] RETURNS [Day] ~ { RETURN [IF d=Monday THEN Sunday ELSE d.PRED] }; Config: TYPE ~ REF ConfigRep; ConfigRep: TYPE ~ RECORD [ dumpServers: DumpServers, defaultClients: DumpClients, dumpClientHosts: SymTab.Ref, dumpClients: DumpClients, tapeChangeSchedule: TapeChangeSchedules, nServers: INT Ź 0 ]; DumpServers: TYPE ~ LIST OF DumpServer; DumpClients: TYPE ~ Tree; TapeChangeSchedules: TYPE ~ LIST OF TapeChangeSchedule; VirtualTapeDriveName: TYPE ~ ROPE; DumpServer: TYPE ~ REF DumpServerRep; DumpServerRep: TYPE ~ RECORD [ name: VirtualTapeDriveName, -- e.g. SSL-A index: CARD, size: INTEGER, -- in megabytes host: ROPE, -- e.g. sapphire device: ROPE, -- e.g. /dev/rsmt0 comments: ROPE ]; DumpKind: TYPE ~ {none, incrOnly, normal, fullOnly}; DumpClient: TYPE ~ REF DumpClientRep; DumpClientRep: TYPE ~ RECORD [ host: ROPE, fileSystem: ROPE, -- e.g. /dev/rxd0a or "default" hasLocalTape: BOOL Ź FALSE, localTapeIndex: INTEGER Ź 0, size: INTEGER Ź 0, -- in megabytes used: INTEGER Ź 0, -- in megabytes dumpKind: DumpKind Ź none, priority: CARD Ź CARD.LAST, -- small numbers are higher priority volatility: REAL Ź 0.0 , -- fraction of file system expected to change on working days comment: ROPE Ź NIL, didLocally: BOOL Ź FALSE ]; GetClientKey: RedBlackTree.GetKey ~ { RETURN[data] }; CompareClientNames: RedBlackTree.Compare ~ { n1: DumpClient Ź NARROW[k]; n2: DumpClient Ź NARROW[data]; RETURN[Rope.Compare[Rope.Cat[n1.host, " ", n1.fileSystem], Rope.Cat[n2.host, " ", n2.fileSystem]]]; }; TapeChangeSchedule: TYPE ~ RECORD [ date: GMT, -- Monday of the week to which this schedule applies, nullGMT for default permittedDumps: ARRAY Day OF DaySpec ]; DaySpec: TYPE ~ RECORD [ changeTape: BOOL, -- if a new tape is to be used for this day allowFull: BOOL, allowIncremental: BOOL ]; -- [FALSE, FALSE, FALSE] no tape change, no dumping serverHeader: ROPE ~ "[DUMP SERVERS]"; clientHeader: ROPE ~ "[DUMP CLIENTS]"; tcsHeader: ROPE ~ "[TAPE CHANGE SCHEDULE]"; GetPath: PROC [in: IO.STREAM] RETURNS [ROPE] ~ { RETURN[IO.GetTokenRope[in, BetweenWhitespace].token]; }; ParseConfig: PROC [in: STREAM, msgs: STREAM] RETURNS [Config] ~ { <> config: Config Ź NEW[ConfigRep Ź [NIL, RedBlackTree.Create[GetClientKey, CompareClientNames], SymTab.Create[case~FALSE], RedBlackTree.Create[GetClientKey, CompareClientNames], NIL]]; line: ROPE; lineStream: IO.STREAM; ParseError: ERROR ~ CODE; currLine: INT Ź 0; ReadServers: PROC RETURNS[nServers: INT Ź 0] ~ { msgs.PutRope["Reading servers...\n"]; DO ENABLE { IO.Error, Convert.Error, ParseError => { msgs.PutF["Parsing error in line %g of config file near position %g in file.\n", [integer[currLine]], [integer[in.GetIndex[]]] ]; LOOP; }; }; name, machine, device, rest: ROPE; size: REAL; currLine Ź currLine+1; line Ź IO.GetLineRope[in]; IF line.Fetch[0]='[ THEN EXIT; IF line.Fetch[0]='# THEN LOOP; lineStream Ź IO.RIS[line, lineStream]; name Ź GetPath[lineStream]; size Ź lineStream.GetReal[]; machine Ź GetPath[lineStream]; device Ź GetPath[lineStream]; [] Ź lineStream.SkipWhitespace[]; rest Ź lineStream.GetLineRope[! IO.EndOfStream => CONTINUE]; config.dumpServers Ź CONS[ NEW[DumpServerRep Ź [name, nServers, Real.Floor[size*1024], machine, device, rest]], config.dumpServers]; nServers Ź nServers.SUCC; ENDLOOP; }; ReadClients: PROC ~ { msgs.PutRope["Reading clients...\n"]; DO ENABLE { IO.Error, Convert.Error, ParseError => { msgs.PutF["Parsing error in line %g of config file near position %g in file.\n", [integer[currLine]], [integer[in.GetIndex[]]] ]; LOOP; }; }; host, fileSystem, dumpKind, rest: ROPE; priority: CARD Ź 99; volatility: REAL Ź 0.0; client: DumpClient ; currLine Ź currLine+1; line Ź IO.GetLineRope[in]; IF line.Fetch[0]='[ THEN EXIT; IF line.Fetch[0]='# THEN LOOP; lineStream Ź IO.RIS[line, lineStream]; host Ź GetPath[lineStream]; fileSystem Ź GetPath[lineStream]; dumpKind Ź GetPath[lineStream]; IF DumpKindFromRope[dumpKind]#none THEN { priority Ź lineStream.GetCard[]; volatility Ź lineStream.GetReal[]; rest Ź lineStream.GetLineRope[! IO.EndOfStream => CONTINUE]; } ELSE { [] Ź lineStream.GetLineRope[! IO.EndOfStream => CONTINUE]; }; IF NOT Rope.Equal[host, "default"] THEN [] Ź config.dumpClientHosts.Store[host, NIL]; client Ź NEW[DumpClientRep Ź [host, fileSystem, FALSE, 0, 0, 0, DumpKindFromRope[dumpKind], priority, volatility/100, rest]]; IF Rope.Equal[fileSystem, "default"] OR Rope.Equal[host, "default"] THEN config.defaultClients.Insert[client, client] ELSE config.dumpClients.Insert[client, client]; ENDLOOP; }; ReadTCS: PROC ~ { msgs.PutRope["Reading tape change schedules...\n"]; DO ENABLE { IO.Error, Convert.Error, ParseError => { msgs.PutF["Parsing error in line %g of config file near position %g in file.\n", [integer[currLine]], [integer[in.GetIndex[]]] ]; LOOP; }; }; date: ROPE; changeSchedule: TapeChangeSchedule Ź [date~nullGMT, permittedDumps~ALL[[TRUE,FALSE,FALSE]]]; currLine Ź currLine+1; line Ź IO.GetLineRope[in ! IO.EndOfStream => EXIT]; IF line.Fetch[0]='[ THEN EXIT; IF line.Fetch[0]='# THEN LOOP; lineStream Ź IO.RIS[line, lineStream]; date Ź GetPath[lineStream]; IF Rope.Equal[date, "default"] THEN changeSchedule.date Ź nullGMT ELSE changeSchedule.date Ź Convert.TimeFromRope[date]; FOR day: Day IN [Day.FIRST .. Day.LAST] DO DO tokenKind: IO.TokenKind; token: ROPE; [tokenKind, token] Ź lineStream.GetCedarTokenRope[]; SELECT tokenKind FROM tokenSINGLE => SELECT token.Fetch[0] FROM '- => {changeSchedule.permittedDumps[day].changeTape Ź FALSE; EXIT}; '+ => {changeSchedule.permittedDumps[day].changeTape Ź FALSE; LOOP }; ENDCASE => ERROR ParseError; tokenID => SELECT TRUE FROM Rope.Equal[token, "F"], Rope.Equal[token, "full"], Rope.Equal[token, "norm"], Rope.Equal[token, "N"] => { changeSchedule.permittedDumps[day].allowFull Ź TRUE; changeSchedule.permittedDumps[day].allowIncremental Ź TRUE; EXIT; }; Rope.Equal[token, "I"], Rope.Equal[token, "inc"] => { changeSchedule.permittedDumps[day].allowIncremental Ź TRUE; EXIT; }; ENDCASE => ERROR ParseError; ENDCASE => ERROR ParseError; ENDLOOP; ENDLOOP; config.tapeChangeSchedule Ź CONS[ changeSchedule, config.tapeChangeSchedule]; ENDLOOP; }; DO ENABLE { IO.EndOfStream => EXIT; }; SELECT TRUE FROM Rope.CompareSubstrs[s1: line, len1: serverHeader.Length[], s2: serverHeader] = equal => config.nServers Ź ReadServers[]; Rope.CompareSubstrs[s1: line, len1: clientHeader.Length[], s2: clientHeader] = equal => ReadClients[]; Rope.CompareSubstrs[s1: line, len1: tcsHeader.Length[], s2: tcsHeader] = equal => ReadTCS[]; ENDCASE => { currLine Ź currLine+1; line Ź in.GetLineRope[] }; ENDLOOP; FinishConfig[config, msgs]; RETURN[config]; }; DFDone: ENTRY UnixSpawnTCP.FinishProc ~ { dfCommand: ROPE Ź NARROW[clientData]; IF dfCommand=currentDfCommand THEN { currentDfCommand Ź NIL; BROADCAST dfDone; }; }; dfDone: CONDITION; currentDfCommand: ROPE; WaitForDFDone: ENTRY PROC [] RETURNS [reallyDone: BOOL] ~ TRUSTED { ENABLE UNWIND => NULL; Process.EnableAborts[@dfDone]; Process.SetTimeout[@dfDone, Process.SecondsToTicks[60]]; IF currentDfCommand # NIL THEN WAIT dfDone; RETURN[currentDfCommand=NIL]; }; BetweenWhitespace: IO.BreakProc ~ {RETURN[ SELECT char FROM IN [IO.NUL .. IO.SP] => sepr, ENDCASE => other]; }; FinishConfig: PROC [c: Config, msgs: IO.STREAM] ~ { <> <> HasLocalTape: PROC [host: ROPE] RETURNS [BOOL, INT] ~ { FOR s: DumpServers Ź c.dumpServers, s.rest WHILE s#NIL DO IF Rope.Equal[host, s.first.host] THEN RETURN [TRUE, s.first.index]; ENDLOOP; RETURN[FALSE, -1]; }; EachHost: SymTab.EachPairAction ~ { host: ROPE Ź NARROW[key]; tryDefaultHostClient: DumpClient Ź NEW[DumpClientRep Ź [host, "default"]]; defaultHostClient: DumpClient Ź NARROW[c.defaultClients.Lookup[tryDefaultHostClient]]; dfOutput: STREAM Ź IO.ROS[]; dfCommand: ROPE Ź currentDfCommand Ź Rope.Cat["/usr/ucb/rsh -n ", host, " df 2> /dev/null | /project/dumps/findRawDevices"]; <> spawnData: REF UnixSpawnTCP.SpawnData Ź UnixSpawnTCP.Spawn[command~dfCommand, out: dfOutput, finish: DFDone, clientData: dfCommand]; msgs.PutF1["Enumerating file systems on %g\n", [rope[host]]]; IF NOT WaitForDFDone[] THEN { msgs.PutF1["host %g did not respond in 60 seconds.\n", [rope[host]] ]; UnixSpawnTCP.Kill[spawnData]; } ELSE { dfOutputRope: ROPE Ź IO.RopeFromROS[dfOutput]; dfIn: STREAM Ź IO.RIS[dfOutputRope]; { ENABLE { IO.EndOfStream => CONTINUE; IO.Error, Convert.Error => { msgs.PutF["Error parsing df output from host %g near position %g.\n", [rope[host]], [integer[dfIn.GetIndex[]]] ]; }; }; msgs.PutF1["%g's file systems:\n", [rope[host]] ]; DO fileSystem: ROPE Ź dfIn.GetTokenRope[BetweenWhitespace].token; size: CARD Ź (dfIn.GetCard[]+1023)/1024; used: CARD Ź (dfIn.GetCard[]+1023)/1024; avail: CARD Ź dfIn.GetCard[]; capacity: ROPE Ź dfIn.GetTokenRope[BetweenWhitespace].token; mountPoint: ROPE Ź dfIn.GetTokenRope[BetweenWhitespace].token; dumpClient: DumpClient Ź NEW[DumpClientRep Ź [host, fileSystem, FALSE, 0, size, used, normal, 99, 0.0, NIL]]; existingClient: DumpClient; msgs.PutF1[ "\t%g\n", [rope[fileSystem]] ]; IF (existingClient Ź NARROW[c.dumpClients.Lookup[dumpClient]])#NIL THEN { existingClient.size Ź size; existingClient.used Ź used; [existingClient.hasLocalTape, existingClient.localTapeIndex] Ź HasLocalTape[existingClient.host]; IF existingClient.comment=NIL THEN existingClient.comment Ź Rope.Concat["# ", mountPoint]; } ELSE { defaultMountPoint: ROPE ~ IF Rope.Equal[mountPoint, Rope.Concat["/", host]] THEN "/machine" ELSE mountPoint; tryDefaultFSClient: DumpClient Ź NEW[DumpClientRep Ź ["default", defaultMountPoint]]; defaultFSClient: DumpClient Ź NARROW[c.defaultClients.Lookup[tryDefaultFSClient]]; defaultClient: DumpClient Ź IF defaultFSClient#NIL THEN defaultFSClient ELSE defaultHostClient; IF defaultClient#NIL THEN { [dumpClient.hasLocalTape, dumpClient.localTapeIndex] Ź HasLocalTape[dumpClient.host]; dumpClient.dumpKind Ź defaultClient.dumpKind; dumpClient.priority Ź defaultClient.priority; dumpClient.volatility Ź defaultClient.volatility; dumpClient.comment Ź Rope.Concat["# ", mountPoint]; c.dumpClients.Insert[dumpClient, dumpClient]; } ELSE { msgs.PutF["skipping file system %g on host %g because it is not an explicit client and there is no applicable default client\n", [rope[fileSystem]], [rope[host]] ]; }; } ENDLOOP; }; }; }; [] Ź c.dumpClientHosts.Pairs[EachHost]; }; DumpKindFromRope: PROC [r: ROPE] RETURNS [DumpKind] ~ { SELECT TRUE FROM Rope.Equal[r, "full", FALSE] => RETURN [fullOnly]; Rope.Equal[r, "incr", FALSE] => RETURN [incrOnly]; Rope.Equal[r, "none", FALSE] => RETURN [none]; Rope.Equal[r, "-", FALSE] => RETURN [none]; Rope.Equal[r, "norm", FALSE] => RETURN [normal]; ENDCASE => ERROR; }; Tape: TYPE ~ REF TapeRep; TapeRep: TYPE ~ RECORD [ dumpServer: DumpServer, day: Day, used: CARD, -- in megabytes remaining: INTEGER, -- in megabytes capacity: INTEGER, useForFullDumps: BOOL, -- full dumps are allowed on this tape maxForFullDumps: INTEGER, currentForFullDumps: INTEGER, estimatedIncremental: INTEGER, headRoom: INTEGER -- = capacity - (maxForFullDumps+estimatedIncremental) ]; Drive: TYPE ~ ARRAY Day OF Tape Ź ALL[NIL]; Tapes: TYPE ~ REF TapesRep; TapesRep: TYPE ~ RECORD [ SEQUENCE nDrives: CARDINAL OF Drive ]; GetTapes: PROC [dumpServers: DumpServers, nServers: INT, changeSchedule: TapeChangeSchedule] RETURNS [tapes: Tapes] ~ { <> tapes Ź NEW[TapesRep[nServers]]; FOR sl: DumpServers Ź dumpServers, sl.rest WHILE sl # NIL DO s: DumpServer Ź sl.first; FOR d: Day IN [Day.FIRST..Day.LAST] DO thisTape: Tape ~ IF changeSchedule.permittedDumps[d].changeTape THEN NEW[TapeRep Ź [s, d, 0, s.size, s.size, changeSchedule.permittedDumps[d].allowFull, 0, 0, 0, s.size]] ELSE tapes[s.index][PrevDay[d]]; tapes[s.index][d] Ź thisTape; ENDLOOP; <> <> FOR d: Day IN [Day.FIRST..Day.LAST] WHILE tapes[s.index][d] = NIL DO tapes[s.index][d] Ź tapes[s.index][PrevDay[d]]; ENDLOOP; ENDLOOP; }; WeeklySchedule: TYPE ~ REF WeeklyScheduleRep; WeeklyScheduleRep: TYPE ~ RECORD [ startDay: GMT, dumps: PQ, -- of DumpItem tapes: Tapes ]; DumpLevel: TYPE ~ { full, incremental, none }; DumpLevelRope: ARRAY DumpLevel OF ROPE ~ ["0", "5", "-"]; DumpItem: TYPE ~ REF DumpItemRep; DumpItemRep: TYPE ~ RECORD [ name: VirtualTapeDriveName, -- e.g. SSL-A host: ROPE, fileSystem: ROPE, dailyDumpInstruction: ARRAY Day OF DumpLevel, priority: CARD, comments: ROPE ]; CompareDumpItems: PriorityQueue.SortPred ~ { d1: DumpItem Ź NARROW[x]; d2: DumpItem Ź NARROW[y]; IF Rope.Compare[d1.name, d2.name, FALSE]=less THEN RETURN[TRUE] ELSE IF Rope.Compare[d1.name, d2.name, FALSE]=greater THEN RETURN[FALSE] ELSE IF d1.priority < d2.priority THEN RETURN [TRUE] ELSE IF d1.priority > d2.priority THEN RETURN [FALSE] ELSE RETURN [Rope.Compare[Rope.Cat[d1.host, " ", d1.fileSystem], Rope.Cat[d2.host, " ", d2.fileSystem]]=less] }; WeeklySchedules: TYPE ~ LIST OF WeeklySchedule; ComputeWeeklySchedules: PROC [config: Config, schedList: LIST OF GMT, msgs: IO.STREAM] RETURNS [ WeeklySchedules ] ~ { <> InSchedList: PROC [start: GMT] RETURNS [BOOL Ź FALSE] ~ { IF schedList=NIL THEN RETURN [TRUE]; FOR l: LIST OF GMT Ź schedList, l.rest WHILE l#NIL DO IF l.first=start THEN RETURN[TRUE]; ENDLOOP; }; result: LIST OF WeeklySchedule Ź NIL; FOR tcs: TapeChangeSchedules Ź config.tapeChangeSchedule, tcs.rest WHILE tcs#NIL DO IF NOT InSchedList[tcs.first.date] THEN LOOP; { tapes: Tapes Ź GetTapes[config.dumpServers, config.nServers, tcs.first]; msgs.PutF1["Computing schedule for %g.\n", IF tcs.first.date=nullGMT THEN [rope["default"]] ELSE [time[tcs.first.date]] ]; result Ź CONS[ComputeOneSchedule[tapes, tcs.first, config.dumpClients, msgs], result]; } ENDLOOP; RETURN[result]; }; ComputeOneSchedule: PROC [tapes: Tapes, tcs: TapeChangeSchedule, dumpClients: DumpClients, msgs: IO.STREAM] RETURNS [ WeeklySchedule ]~ { <> <> <<1. In priority order, in decreasing size order, assign full dump and following incrementals>> <> <<2. In decreasing size order, assign full dump and following incrementals; sort each tape into priority order.>> <> AssignLocally: PROC [client: DumpClient, tape: Tape] RETURNS [BOOL Ź TRUE] ~ { incrCount: CARD Ź IF client.dumpKind=incrOnly THEN 10 ELSE 1; thisDumpItem: DumpItem Ź NEW[DumpItemRep Ź [tape.dumpServer.name, client.host, client.fileSystem, ALL[none], client.priority, client.comment]]; IF client.dumpKind IN [normal..fullOnly] AND tape.useForFullDumps THEN { IF tape.remaining < client.size THEN RETURN[FALSE]; thisDumpItem.dailyDumpInstruction[tape.day] Ź full; } ELSE IF client.dumpKind=incrOnly OR (client.dumpKind IN [normal..fullOnly] AND NOT tape.useForFullDumps) THEN { incrSize: INTEGER Ź ComputeIncrementalSize[client, incrCount]; incrCount Ź 10; -- only incrementals; use gross size estimate IF tcs.permittedDumps[tape.day].allowIncremental THEN { IF tape.remaining < incrSize THEN RETURN[FALSE]; thisDumpItem.dailyDumpInstruction[tape.day] Ź incremental; } }; FOR day: Day Ź NextDay[tape.day], NextDay[day] WHILE day#tape.day DO incrTape: Tape Ź tapes[tape.dumpServer.index][day]; IF client.dumpKind=fullOnly AND tcs.permittedDumps[day].allowFull THEN { IF incrTape.remaining < client.size THEN RETURN[FALSE]; thisDumpItem.dailyDumpInstruction[day] Ź full; incrCount Ź 0; } ELSE IF client.dumpKind IN [incrOnly..normal] OR client.dumpKind=fullOnly AND NOT tcs.permittedDumps[day].allowFull THEN { incrSize: INTEGER Ź ComputeIncrementalSize[client, incrCount]; IF incrTape#NIL AND tcs.permittedDumps[day].allowIncremental THEN { IF incrTape.remaining < incrSize THEN RETURN[FALSE]; thisDumpItem.dailyDumpInstruction[day] Ź incremental; }; }; incrCount Ź incrCount+1; ENDLOOP; <> incrCount Ź 10; IF thisDumpItem.dailyDumpInstruction[tape.day] = full THEN { DeductFullDump[tape, client]; incrCount Ź 1 } ELSE { DeductIncrementalDump[tape, client, incrCount]; }; FOR day: Day Ź NextDay[tape.day], NextDay[day] WHILE day#tape.day DO IF thisDumpItem.dailyDumpInstruction[day] = full THEN { DeductFullDump[tape, client]; incrCount Ź 0; } ELSE { DeductIncrementalDump[tape, client, incrCount]; }; incrCount Ź incrCount+1; ENDLOOP; thisWeeksSchedule.dumps.Insert[thisDumpItem]; }; DeductFullDump: PROC [tape: Tape, client: DumpClient] ~ { tape.remaining Ź tape.remaining - client.size; tape.used Ź tape.used + client.size; tape.maxForFullDumps Ź tape.maxForFullDumps + client.size; tape.currentForFullDumps Ź tape.currentForFullDumps + client.used; }; DeductIncrementalDump: PROC [tape: Tape, client: DumpClient, incrCount: INT] ~ { incrSize: INTEGER Ź ComputeIncrementalSize[client, incrCount]; tape.remaining Ź tape.remaining - incrSize; tape.used Ź tape.used + incrSize; tape.estimatedIncremental Ź tape.estimatedIncremental + incrSize; }; Assign: PROC [client: DumpClient, tape: Tape] ~ { NoRoomForFull: PROC [client: DumpClient, remaining: INTEGER] ~ { msgs.PutFL["%g %g needs %g megabytes but the biggest available space is only %g megabytes.\n", LIST[[rope[client.host]], [rope[client.fileSystem]], [cardinal[client.size]], [integer[remaining]]] ]; done Ź FALSE; }; NoRoomForIncr: PROC [client: DumpClient, required, remaining: INTEGER] ~ { msgs.PutFL["%g %g needs %g megabytes but the incremental tape has only %g megabytes.\n", LIST[[rope[client.host]], [rope[client.fileSystem]], [cardinal[required]], [integer[remaining]]] ]; done Ź FALSE; }; incrCount: CARD Ź 10; thisDumpItem: DumpItem Ź NEW[DumpItemRep Ź [tape.dumpServer.name, client.host, client.fileSystem, ALL[none], client.priority, client.comment]]; [] Ź tapeHeap.Delete[tape]; IF client.dumpKind IN [normal..fullOnly] AND tape.useForFullDumps THEN { IF tape.remaining < client.size THEN NoRoomForFull[client, tape.remaining]; DeductFullDump[tape, client]; thisDumpItem.dailyDumpInstruction[tape.day] Ź full; incrCount Ź 1; } ELSE IF client.dumpKind=incrOnly OR (client.dumpKind IN [normal..fullOnly] AND NOT tape.useForFullDumps) THEN { incrSize: INTEGER Ź ComputeIncrementalSize[client, incrCount]; IF tcs.permittedDumps[tape.day].allowIncremental THEN { IF tape.remaining < incrSize THEN NoRoomForIncr[client, incrSize, tape.remaining]; DeductIncrementalDump[tape, client, incrCount]; thisDumpItem.dailyDumpInstruction[tape.day] Ź incremental; } }; tapeHeap.Insert[tape, tape]; FOR day: Day Ź NextDay[tape.day], NextDay[day] WHILE day#tape.day DO incrTape: Tape Ź tapes[tape.dumpServer.index][day]; [] Ź tapeHeap.Delete[incrTape]; IF client.dumpKind=fullOnly AND tcs.permittedDumps[day].allowFull THEN { IF incrTape.remaining < client.size THEN NoRoomForIncr[client, client.size, incrTape.remaining]; DeductFullDump[incrTape, client]; thisDumpItem.dailyDumpInstruction[day] Ź full; incrCount Ź 0; } ELSE IF client.dumpKind IN [incrOnly..normal] OR client.dumpKind=fullOnly AND NOT tcs.permittedDumps[day].allowFull THEN { incrSize: INTEGER Ź ComputeIncrementalSize[client, incrCount]; IF incrTape#NIL AND tcs.permittedDumps[day].allowIncremental THEN { IF incrTape.remaining < incrSize THEN NoRoomForIncr[client, incrSize, incrTape.remaining]; DeductIncrementalDump[incrTape, client, incrCount]; thisDumpItem.dailyDumpInstruction[day] Ź incremental; }; }; tapeHeap.Insert[incrTape, incrTape]; incrCount Ź incrCount+1; ENDLOOP; thisWeeksSchedule.dumps.Insert[thisDumpItem]; }; FindBest: PROC [drive: Drive] RETURNS [Tape] ~ { bestTape: Tape Ź drive[Day.FIRST]; FOR day: Day IN [Day.FIRST.SUCC..Day.LAST] DO IF CompareTapes[drive[day], bestTape]=greater THEN { bestTape Ź drive[day]; }; ENDLOOP; RETURN[bestTape]; }; tapeHeap: Tree; clientHeap: PQ; done: BOOL Ź TRUE; thisWeeksSchedule: WeeklySchedule Ź NEW[WeeklyScheduleRep Ź [tcs.date, NIL, tapes]]; msgs.PutRope["Trying considering priority first\n"]; InitTapes[tapes]; thisWeeksSchedule.dumps Ź PriorityQueue.Create[CompareDumpItems]; <> clientHeap Ź MakeClientHeap[dumpClients, priorityFirst, TRUE]; WHILE clientHeap.Size[]#0 DO client: DumpClient Ź NARROW[clientHeap.Remove[]]; tape: Tape Ź FindBest[tapes[client.localTapeIndex]]; client.didLocally Ź AssignLocally[client, tape]; ENDLOOP; <> tapeHeap Ź MakeTapeHeap[tapes]; clientHeap Ź MakeClientHeap[dumpClients, priorityFirst, FALSE]; WHILE clientHeap.Size[]#0 DO client: DumpClient Ź NARROW[clientHeap.Remove[]]; tape: Tape Ź NARROW[tapeHeap.LookupLargest[]]; Assign[client, tape]; ENDLOOP; IF done THEN RETURN[thisWeeksSchedule]; -- worked first time msgs.PutRope["Trying again, considering size first\n"]; InitTapes[tapes]; thisWeeksSchedule.dumps Ź PriorityQueue.Create[CompareDumpItems]; <> clientHeap Ź MakeClientHeap[dumpClients, sizeFirst, TRUE]; WHILE clientHeap.Size[]#0 DO client: DumpClient Ź NARROW[clientHeap.Remove[]]; tape: Tape Ź FindBest[tapes[client.localTapeIndex]]; client.didLocally Ź AssignLocally[client, tape]; ENDLOOP; <> tapeHeap Ź MakeTapeHeap[tapes]; clientHeap Ź MakeClientHeap[dumpClients, sizeFirst]; <> WHILE clientHeap.Size[]#0 DO client: DumpClient Ź NARROW[clientHeap.Remove[]]; tape: Tape Ź NARROW[tapeHeap.LookupLargest[]]; Assign[client, tape]; ENDLOOP; RETURN[thisWeeksSchedule] }; ProduceWeeklySchedule: PROC [s: WeeklySchedule, out: STREAM] ~ { <> IF s.startDay = BasicTime.nullGMT THEN out.PutRope["\n# The default schedule"] ELSE out.PutF1["\n# Schedule for week beginning %g", [rope[Convert.RopeFromTime[s.startDay, years, days, TRUE]]] ]; IF s.dumps=NIL THEN out.PutRope["\n No feasible schedule found\n"] ELSE WHILE s.dumps.Size[]#0 DO d: DumpItem Ź NARROW[s.dumps.Remove[]]; out.PutF["\n%g %g %g ", [rope[d.name]], [rope[d.host]], [rope[d.fileSystem]] ]; FOR day: Day IN [Monday..Sunday] DO out.PutRope[DumpLevelRope[d.dailyDumpInstruction[day]]]; out.PutRope[" "]; ENDLOOP; out.PutF1[ "%g", [rope[d.comments]] ]; ENDLOOP; out.PutRope["\n\n# Tape Use\n# Tape used forFull inUse headroom"]; { prevTape: Tape Ź NIL; FOR ds: CARD IN [0..s.tapes.nDrives) DO FOR day: Day IN [Day.FIRST..Day.LAST] DO tape: Tape Ź s.tapes[ds][day]; IF tape=NIL OR tape=prevTape THEN LOOP; out.PutFL["\n# %g(%g) %g %g %g ", LIST [[rope[tape.dumpServer.name]], [rope[Days[day]]], [cardinal[tape.used]], [cardinal[tape.maxForFullDumps]], [cardinal[tape.currentForFullDumps]]] ]; out.PutF1["%g", [integer[tape.headRoomŹ(tape.capacity-tape.used)]] ]; prevTape Ź tape; ENDLOOP; ENDLOOP; }; out.PutRope["\n\n"]; }; ComputeIncrementalSize: PROC [client: DumpClient, incrCount: INT] RETURNS [INT] ~ { v: REAL Ź client.volatility; incrSize: INT Ź Real.Ceiling[v*client.size+v*v*client.size*(incrCount-1)]; RETURN [incrSize]; }; CompareClient: PriorityQueue.SortPred ~ { priorityFirst: BOOL Ź NARROW[data, REF BOOL]; c1: DumpClient Ź NARROW[x]; c2: DumpClient Ź NARROW[y]; IF priorityFirst THEN { IF c1.priority < c2.priority THEN RETURN [TRUE] ELSE IF c2.priority < c1.priority THEN RETURN [FALSE] ELSE RETURN [c1.size >= c2.size]; } ELSE { IF c1.size > c2.size THEN RETURN [TRUE] ELSE IF c2.size > c1.size THEN RETURN [FALSE] ELSE RETURN [c1.priority <= c2.priority]; }; }; MakeClientHeap: PROC [clients: DumpClients, key: {priorityFirst, sizeFirst}, localOnly: BOOL Ź FALSE] RETURNS [PQ] ~ { pq: PQ ~ PriorityQueue.Create[ CompareClient, NEW[BOOL Ź key=priorityFirst]]; EachClient: RedBlackTree.EachNode ~ { dumpClient: DumpClient Ź NARROW[data]; IF NOT localOnly AND NOT dumpClient.didLocally THEN pq.Insert[data] ELSE IF localOnly THEN { dumpClient.didLocally Ź FALSE; IF dumpClient.hasLocalTape THEN pq.Insert[data] }; }; clients.EnumerateIncreasing[EachClient]; RETURN[pq]; }; GetTapeKey: RedBlackTree.GetKey ~ { RETURN[data] }; CompareTapes: RedBlackTree.Compare ~ { n1: Tape Ź NARROW[k]; n2: Tape Ź NARROW[data]; IF n1.useForFullDumps AND NOT n2.useForFullDumps THEN RETURN [greater]; IF n2.useForFullDumps AND NOT n1.useForFullDumps THEN RETURN [less]; IF n1.remaining CONTINUE]; ENDLOOP; ENDLOOP; RETURN[tt]; }; DoIt: PROC [configPath, schedPath, specialWeekPath: PFS.PATH, schedList: LIST OF GMT, msgs: IO.STREAM] ~ { configStream: IO.STREAM ~ PFS.StreamOpen[configPath ! PFS.Error => {msgs.PutF1["Couldn't open input file %g\n", [rope[PFS.RopeFromPath[configPath]]]]; GOTO out}]; config: Config ~ ParseConfig[configStream, msgs]; ws: WeeklySchedules Ź ComputeWeeklySchedules[config, schedList, msgs]; configStream.Close[]; FOR sched: WeeklySchedules Ź ws, sched.rest WHILE sched # NIL DO schedStream: IO.STREAM; IF sched.first.startDay = nullGMT THEN { ENABLE PFS.Error => {msgs.PutF1["Couldn't open output file %g\n", [rope[PFS.RopeFromPath[schedPath]]]]; LOOP}; msgs.PutF1["writing %g\n", [rope[PFS.RopeFromPath[schedPath]]]]; schedStream Ź PFS.StreamOpen[schedPath, create]; } ELSE { datedPath: PFS.PATH ~ MakeDatedPath[specialWeekPath, sched.first.startDay]; { ENABLE PFS.Error => {msgs.PutF1["Couldn't open output file %g\n", [rope[PFS.RopeFromPath[datedPath]]]]; LOOP}; msgs.PutF1["writing %g\n", [rope[PFS.RopeFromPath[datedPath]]]]; schedStream Ź PFS.StreamOpen[datedPath, create]; } }; ProduceWeeklySchedule[ sched.first, schedStream ]; schedStream.Close[]; ENDLOOP; EXITS out => NULL }; MakeDatedPath: PROC [path: PFS.PATH, time: GMT] RETURNS [PFS.PATH] ~ { undatedName: ROPE ~ PFSNames.ComponentRope[PFSNames.ShortName[path]]; unpacked: BasicTime.Unpacked ~ BasicTime.Unpack[time]; ymd: ROPE ~ Rope.Cat[ Rope.Substr[Convert.RopeFromCard[unpacked.year], 2], ".", IF unpacked.month < October THEN "0" ELSE NIL, Convert.RopeFromCard[ORD[unpacked.month]+1], Rope.Cat[".", IF unpacked.day < 10 THEN "0" ELSE NIL, Convert.RopeFromCard[ORD[unpacked.day]] ] ]; datedName: ROPE ~ undatedName.Cat[".", ymd]; RETURN[PFSNames.ReplaceShortName[path, [[datedName, 0, datedName.Length[]]]]]; }; configSuffix: ROPE ~ ".dump_config"; weeklySuffix: ROPE ~ ".weekly_schedule"; specialWeekSuffix: ROPE ~ ".week_of"; ComputeScheduleCommand: Commander.CommandProc ~ { argv: CommanderOps.ArgumentVector Ź CommanderOps.Parse[cmd]; IF argv.argc < 2 THEN GOTO usage; { input: ROPE ~ argv[1]; inputPath: PFS.PATH Ź PFS.PathFromRope[input]; outputPath: PFS.PATH; specialWeekPath: PFS.PATH; shortName: ROPE Ź PFSNames.ComponentRope[PFSNames.ShortName[inputPath]]; schedList: LIST OF GMT; dotPos: INT ~ shortName.FindBackward["."]; IF dotPos # -1 THEN { shortName Ź shortName.Substr[0, dotPos]; } ELSE { inputName: ROPE ~ shortName.Concat[configSuffix]; inputPath Ź PFSNames.ReplaceShortName[inputPath, [[inputName, 0, inputName.Length[]]]]; }; { outputName: ROPE ~ shortName.Concat[weeklySuffix]; specialWeekName: ROPE ~ shortName.Concat[specialWeekSuffix]; outputPath Ź PFSNames.ReplaceShortName[inputPath, [[outputName, 0, outputName.Length[]]]]; specialWeekPath Ź PFSNames.ReplaceShortName[inputPath, [[specialWeekName, 0, specialWeekName.Length[]]]]; }; FOR argp: INT IN [2..argv.argc) DO IF Rope.Equal[argv[argp], "default"] THEN schedList Ź CONS[BasicTime.nullGMT, schedList] ELSE schedList Ź CONS[Convert.TimeFromRope[argv[argp] ! Convert.Error => CONTINUE], schedList]; ENDLOOP; { DoIt[inputPath, outputPath, specialWeekPath, schedList, cmd.out]; }; } EXITS usage => { cmd.out.PutRope["ScheduleDumps "]; cmd.out.PutRope[helpMsg]; } }; helpMsg: ROPE ~ "configFileName {MM/DD/YY | default}*\n Writes dump schedule files for the weeks specified (or all specified in the config if none specified on the command line). configFileName suffix defaults to dump_config if it doesn't have a suffix." ; Commander.Register["ScheduleDumps", ComputeScheduleCommand, helpMsg]; END. December 1, 1991 <> <> <> <> <> <> <> <> <> <<>> <> <> <> <> <> <>