RZ

001: // ConReservation.cc # the actual synthesize algorithm
002:
003: #include <cassert>
004: #include <sys/mman.h>
005:
006: #include <vector>
007: #include <algorithm>
008: //#include <utility>
009:
010: #include "RZError.hh"
011: #include "RZMagic.hh"
012: #include "RZIO.hh"
013: #include "DataPackets.hh"
014: #include "ExtractRemoteCon.hh"
015: #include "ConReservation.hh"
016:
017: // ######## ######## ######## ######## ######## ######## ######## ########
018:
019: void RZ::ConReservation::writeremotetab(int at, int to)
020: {
021:     if (at >= (int)rz_wrapper.n_blks) return;
022:     if (to >= (int)rz_wrapper.n_blks) to = rz_wrapper.n_blks;
023:     if (to <= 0) return;
024:     if (at <= 0) at = 0;
025:
026:     if (at > to) throw AssertionError();
027:
028:     for (int i = at; i < to; ++i) reservation_tables.rtab_mmap[ i ] = -1;
029: }       
030:
031: // ######## ######## ######## ######## ######## ######## ######## ########
032:
033: // by a simple linear scan from $fwdi finds first local block or past-the-end
034: //   $fwdsize is incremented by the block sizes
035: //   $sizelimit is reduced by the block sizes
036: // however: if $sizelimit becomes negative the scanning stops
037: // before scanning starts $sizelimit is the minimum of passed argument
038: //   and by file size remaining -- if argument negative it is thrown away
039: // returned $sizelimit is
040: //   0 if linear scan reaches past-the-end
041: //   >= 0 if linear finds a local block
042: //   < 0 if $sizelimit broached without finding a local block
043: void RZ::ConReservation::fwdfindlocal(int &fwdi, int &fwdsize, int &sizelimit)
044: {
045:     if (fwdi < rz_wrapper.rz_at_begin || rz_wrapper.rz_at_end < fwdi)
046:         throw AssertionError("fwdi = $fwdi out of range.  Died");
047:
048:     {
049:         int fileremaining = rz_wrapper.rz_end - rz_wrapper.rz_at[ fwdi ];
050:         if (sizelimit < 0 || fileremaining < sizelimit) {
051:             sizelimit = fileremaining;
052:         }
053:     }
054:
055:     if (fwdi == -1) {
056:         // force initial offset packet to be included
057:         {
058:             unsigned int rzsize = rz_wrapper.rz_to[ -1 ];
059:             fwdsize += rzsize;
060:             sizelimit -= rzsize;
061:         }
062:         ++fwdi;
063:     }
064:     //findfirst
065:     for (; fwdi < (int)rz_wrapper.n_blks; ++fwdi) {
066:         if (sizelimit < 0) break;
067:         if (reservation_tables.ltab_mmap[ fwdi ]) break;
068:         {
069:             unsigned int rzsize = rz_wrapper.rz_size(fwdi);
070:             fwdsize += rzsize;
071:             sizelimit -= rzsize;
072:         }
073:     }
074:     if (fwdi == (int)rz_wrapper.n_blks && fwdi < rz_wrapper.rz_at_end) {
075:         // force final cap packet to be included
076:         {
077:             unsigned int rzsize = rz_wrapper.rz_size(fwdi);
078:             fwdsize += rzsize;
079:             sizelimit -= rzsize;
080:         }
081:         ++fwdi;
082:     }
083: }       
084:
085: // works just like fwdfindlocal above
086: void RZ::ConReservation::fwdfindremote(int &fwdi, int &fwdsize, int &sizelimit)
087: {
088:     if (fwdi < rz_wrapper.rz_at_begin || rz_wrapper.rz_at_end < fwdi)
089:         throw AssertionError("fwdi = $fwdi out of range.  Died");
090:
091:     {
092:         int fileremaining = rz_wrapper.rz_end - rz_wrapper.rz_at[ fwdi ];
093:         if (sizelimit < 0 || fileremaining < sizelimit) {
094:             sizelimit = fileremaining;
095:         }
096:     }
097:
098:     // initial offset packet is never local
099:     if (fwdi < 0) return;
100:     // final cap packet is never local
101:     if (fwdi >= (int)rz_wrapper.n_blks) return;
102:     for (; fwdi < (int)rz_wrapper.n_blks; ++fwdi) {
103:         if (sizelimit < 0) break;
104:         if (!reservation_tables.ltab_mmap[ fwdi ]) break;
105:         {
106:             unsigned int rzsize = rz_wrapper.rz_size(fwdi);
107:             fwdsize += rzsize;
108:             sizelimit -= rzsize;
109:         }
110:     }
111: }       
112:
113: // ######## ######## ######## ######## ######## ######## ######## ########
114:
115: void RZ::ConReservation::fwdlocalskip(
116:     std::vector< int > &f, int packetlimit,
117:     int &localsize, int &remotesize, int &nextsize, int &remaining)
118: {
119:     int forth = f.back();
120:     f.pop_back();
121:
122:     for (;;) {
123:         if (forth == rz_wrapper.rz_at_end) {
124:             f.push_back(forth);
125:             localsize = 0; remotesize = 0;
126:             nextsize = 0; remaining = 0;
127:             return; // ( 0, 0, 0, 0 )
128:         }
129:
130:         int further = forth, furthersz = 0, limit = packetlimit;
131:         fwdfindlocal(further, furthersz, limit);
132:
133:         if (limit <= 0) {
134:             f.push_back(forth);
135:             f.push_back(further);
136:             localsize = 0; remotesize = furthersz;
137:             nextsize = 0; remaining = limit;
138:             return; // ( 0, furthersz, 0, limit )
139:         }
140:
141:         int furthest = further, furthestsz = 0, ignore = -1;
142:         fwdfindremote(furthest, furthestsz, ignore);
143:
144:         if (further > forth) {
145:             f.push_back(forth);
146:             f.push_back(further);
147:             f.push_back(furthest);
148:             localsize = 0; remotesize = furthersz;
149:             nextsize = furthestsz; remaining = limit;
150:             return; // ( 0, furthersz, furthestsz, limit )
151:         }
152:
153:         forth = furthest;
154:     }
155: }
156:         
157: void RZ::ConReservation::fwdlocalinterval(
158:     std::vector< int > &f, int limit,
159:     int &localsize, int &remotesize, int &nextsize, int &remaining)
160: {
161:     int forth = f.back();
162:     f.pop_back();
163:     int forthsz = 0;
164:
165:     for (;;) {
166:         if (forth == rz_wrapper.rz_at_end || limit <= 0) {
167:             f.push_back(forth);
168:             localsize = forthsz; remotesize = 0; nextsize = 0; remaining = 0;
169:             return; // ( forthsz, 0, 0, 0 )
170:         }
171:
172:         int further = forth, furthersz = 0;
173:         fwdfindlocal(further, furthersz, limit);
174:
175:         if (limit <= 0) {
176:             f.push_back(forth);
177:             f.push_back(further);
178:             localsize = forthsz; remotesize = furthersz;
179:             nextsize = 0; remaining = limit;
180:             return; // ( forthsz, furthersz, 0, limit )
181:         }
182:
183:         int furthest = further, furthestsz = 0, ignore = -1;
184:         fwdfindremote(furthest, furthestsz, ignore);
185:
186:         if (further > forth) {
187:             f.push_back(forth);
188:             f.push_back(further);
189:             f.push_back(furthest);
190:             localsize = forthsz; remotesize = furthersz;
191:             nextsize = furthestsz; remaining = limit;
192:             return; // ( forthsz, furthersz, furthestsz, limit )
193:         }
194:
195:         forth = furthest;
196:         forthsz += furthestsz;
197:         limit -= forthsz;
198:     }
199: }
200:         
201: // ######## ######## ######## ######## ######## ######## ######## ########
202:
203: void RZ::ConReservation::fwdcontiguousinterval(
204:     std::vector< int > &f, int packetlimit, int &fbegin, int &fend, int &fnext)
205: {
206:     // invocation fwdcontiguousinterval([ $fwdborder ], $packetlimit);
207:
208:     // initial step forward
209:     int localsize, remotesize, nextsize, limit;
210:     fwdlocalskip(f, packetlimit, localsize, remotesize, nextsize, limit);
211:
212:     if (limit <= 0) {
213:         fbegin = f.front(); fend = f.back(); fnext = f.back();
214:         return; // @{$f}[ 0, -1, -1 ]
215:     }
216:
217:     // potential additional steps to create an unbroken interval
218:     // ibegin = 0, iend = 1, inext = 2
219:     for (int iend = 1, inext = 2;;) {
220:         // we reduce server load by combining nearby remote ranges
221:         // into one larger range, ignoring the local availabilty of
222:         // intervening blocks
223:         //
224:         // ( it is actually possible to request discontiguous ranges )
225:         // ( it complicates the retrieval code and may not be well )
226:         // ( supported by servers --- hovever it may be necessary )
227:         //
228:         // use tuneable ratios to try and get this process right
229:         //
230:         // note that we are working at cross purposes to the
231:         // packet size limit which breaks up large packets in order
232:         // to give the local scanner a chance to identify more blocks
233:         // 
234:         // the packet size limiting logic is braindead --- am hoping
235:         // that geometric growth will hide the flaws
236:
237:         limit -= nextsize;
238:
239:         if (limit <= 0) {
240:             fbegin = f.front(); fend = f[ iend ]; fnext = f[ inext ];
241:             return;
242:         }
243:
244:         {
245:             int l, r, n, limit;
246:             fwdlocalinterval(f, limit, l, r, n, limit);
247:
248:             l += nextsize;
249:             nextsize = n;
250:
251:             if (l > packetlimit * DataPackets::MARGINAL_THRESHOLD) {
252:                 fbegin = f.front(); fend = f[ iend ]; fnext = f[ inext ];
253:                 return;
254:             }
255:
256:             localsize += l;
257:             remotesize += r;
258:         }
259:
260:         // int ratio = localsize / (remotesize + localsize);
261:
262:         if (localsize > packetlimit * DataPackets::PACKET_THRESHOLD) {
263:             fbegin = f.front(); fend = f[ iend ]; fnext = f[ inext ];
264:             return;
265:         }
266:
267:         if (limit <= 0) {
268:             fbegin = f.front(); fend = f.back(); fnext = f.back();
269:             return;
270:         }
271:
272:         {
273:             int fend = f.size(); // past-the-end arithmetic
274:             iend = fend - 2;
275:             inext = fend - 1;
276:         }
277:     }
278: }
279:
280: void RZ::ConReservation::fwdmultipleintervals(
281:     std::vector< int > &f, int packetlimit)
282: {
283:     // invocation fwdmultipleintervals([ fwdborder ], packetlimit);
284:
285:     // initial step forward
286:     int ignore1, ignore2, nextsize, limit;
287:     fwdlocalskip(f, packetlimit, ignore1, ignore2, nextsize, limit);
288:
289:     for (;;) {
290:         limit -= nextsize;
291:
292:         if (limit <= 0) return;
293:
294:         fwdlocalskip(f, limit, ignore1, ignore2, nextsize, limit);
295:     }
296: }
297:
298: bool RZ::ConReservation::equalintervals(
299:     std::vector< int > &f, std::vector< int > &g)
300: {
301:     for (unsigned int i = 0; i <= f.size() && i <= g.size(); ++i) {
302:         if (f[ i ] != g[ i ]) return 0;
303:     }
304:
305:     return 1;
306: }
307:
308: // ######## ######## ######## ######## ######## ######## ######## ########
309:
310: // ConReservation.cc # the actual synthesize algorithm