src/HttpHdrRange.cc

   1
   2 /*
   3  * $Id$
   4  *
   5  * DEBUG: section 64    HTTP Range Header
   6  * AUTHOR: Alex Rousskov
   7  *
   8  * SQUID Web Proxy Cache          http://www.squid-cache.org/
   9  * ----------------------------------------------------------
  10  *
  11  *  Squid is the result of efforts by numerous individuals from
  12  *  the Internet community; see the CONTRIBUTORS file for full
  13  *  details.   Many organizations have provided support for Squid's
  14  *  development; see the SPONSORS file for full details.  Squid is
  15  *  Copyrighted (C) 2001 by the Regents of the University of
  16  *  California; see the COPYRIGHT file for full details.  Squid
  17  *  incorporates software developed and/or copyrighted by other
  18  *  sources; see the CREDITS file for full details.
  19  *
  20  *  This program is free software; you can redistribute it and/or modify
  21  *  it under the terms of the GNU General Public License as published by
  22  *  the Free Software Foundation; either version 2 of the License, or
  23  *  (at your option) any later version.
  24  *
  25  *  This program is distributed in the hope that it will be useful,
  26  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  27  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  28  *  GNU General Public License for more details.
  29  *
  30  *  You should have received a copy of the GNU General Public License
  31  *  along with this program; if not, write to the Free Software
  32  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  33  *
  34  */
  35
  36 #include "squid.h"
  37 #include "Store.h"
  38 #include "HttpHeaderRange.h"
  39 #include "client_side_request.h"
  40 #include "HttpReply.h"
  41 #include "StrList.h"
  42
  43 /*
  44  *    Currently only byte ranges are supported
  45  *
  46  *    Essentially, there are three types of byte ranges:
  47  *
  48  *      1) first-byte-pos "-" last-byte-pos  // range
  49  *      2) first-byte-pos "-"                // trailer
  50  *      3)                "-" suffix-length  // suffix (last length bytes)
  51  *
  52  *
  53  *    When Range field is parsed, we have no clue about the content
  54  *    length of the document. Thus, we simply code an "absent" part
  55  *    using HttpHdrRangeSpec::UnknownPosition constant.
  56  *
  57  *    Note: when response length becomes known, we convert any range
  58  *    spec into type one above. (Canonization process).
  59  */
  60
  61 /* local routines */
  62 #define known_spec(s) ((s) > HttpHdrRangeSpec::UnknownPosition)
  63
  64 /* globals */
  65 size_t HttpHdrRange::ParsedCount = 0;
  66 int64_t const HttpHdrRangeSpec::UnknownPosition = -1;
  67
  68 /*
  69  * Range-Spec
  70  */
  71
  72 HttpHdrRangeSpec::HttpHdrRangeSpec() : offset(UnknownPosition), length(UnknownPosition) {}
  73
  74 /* parses range-spec and returns new object on success */
  75 HttpHdrRangeSpec *
  76 HttpHdrRangeSpec::Create(const char *field, int flen)
  77 {
  78     HttpHdrRangeSpec spec;
  79
  80     if (!spec.parseInit(field, flen))
  81         return NULL;
  82
  83     return new HttpHdrRangeSpec(spec);
  84 }
  85
  86 bool
  87 HttpHdrRangeSpec::parseInit(const char *field, int flen)
  88 {
  89     const char *p;
  90
  91     if (flen < 2)
  92         return false;
  93
  94     /* is it a suffix-byte-range-spec ? */
  95     if (*field == '-') {
  96         if (!httpHeaderParseOffset(field + 1, &length))
  97             return false;
  98     } else
  99         /* must have a '-' somewhere in _this_ field */
 100         if (!((p = strchr(field, '-')) || (p - field >= flen))) {
 101             debugs(64, 2, "invalid (missing '-') range-spec near: '" << field << "'");
 102             return false;
 103         } else {
 104             if (!httpHeaderParseOffset(field, &offset))
 105                 return false;
 106
 107             ++p;
 108
 109             /* do we have last-pos ? */
 110             if (p - field < flen) {
 111                 int64_t last_pos;
 112
 113                 if (!httpHeaderParseOffset(p, &last_pos))
 114                     return false;
 115
 116                 // RFC 2616 s14.35.1 MUST: last-byte-pos >= first-byte-pos
 117                 if (last_pos < offset) {
 118                     debugs(64, 2, "invalid (last-byte-pos < first-byte-pos) range-spec near: " << field);
 119                     return false;
 120                 }
 121
 122                 HttpHdrRangeSpec::HttpRange aSpec (offset, last_pos + 1);
 123
 124                 length = aSpec.size();
 125             }
 126         }
 127
 128     return true;
 129 }
 130
 131 void
 132 HttpHdrRangeSpec::packInto(Packer * packer) const
 133 {
 134     if (!known_spec(offset))    /* suffix */
 135         packerPrintf(packer, "-%" PRId64,  length);
 136     else if (!known_spec(length))               /* trailer */
 137         packerPrintf(packer, "%" PRId64 "-", offset);
 138     else                        /* range */
 139         packerPrintf(packer, "%" PRId64 "-%" PRId64,
 140                      offset, offset + length - 1);
 141 }
 142
 143 void
 144 HttpHdrRangeSpec::outputInfo( char const *note) const
 145 {
 146     debugs(64, 5, "HttpHdrRangeSpec::canonize: " << note << ": [" <<
 147            offset << ", " << offset + length <<
 148            ") len: " << length);
 149 }
 150
 151 /* fills "absent" positions in range specification based on response body size
 152  * returns true if the range is still valid
 153  * range is valid if its intersection with [0,length-1] is not empty
 154  */
 155 int
 156 HttpHdrRangeSpec::canonize(int64_t clen)
 157 {
 158     outputInfo ("have");
 159     HttpRange object(0, clen);
 160
 161     if (!known_spec(offset)) {  /* suffix */
 162         assert(known_spec(length));
 163         offset = object.intersection(HttpRange (clen - length, clen)).start;
 164     } else if (!known_spec(length)) {   /* trailer */
 165         assert(known_spec(offset));
 166         HttpRange newRange = object.intersection(HttpRange (offset, clen));
 167         length = newRange.size();
 168     }
 169     /* we have a "range" now, adjust length if needed */
 170     assert(known_spec(length));
 171
 172     assert(known_spec(offset));
 173
 174     HttpRange newRange = object.intersection (HttpRange (offset, offset + length));
 175
 176     length = newRange.size();
 177
 178     outputInfo ("done");
 179
 180     return length > 0;
 181 }
 182
 183 /* merges recepient with donor if possible; returns true on success
 184  * both specs must be canonized prior to merger, of course */
 185 bool
 186 HttpHdrRangeSpec::mergeWith(const HttpHdrRangeSpec * donor)
 187 {
 188     bool merged (false);
 189 #if MERGING_BREAKS_NOTHING
 190     /* Note: this code works, but some clients may not like its effects */
 191     int64_t rhs = offset + length;              /* no -1 ! */
 192     const int64_t donor_rhs = donor->offset + donor->length;    /* no -1 ! */
 193     assert(known_spec(offset));
 194     assert(known_spec(donor->offset));
 195     assert(length > 0);
 196     assert(donor->length > 0);
 197     /* do we have a left hand side overlap? */
 198
 199     if (donor->offset < offset && offset <= donor_rhs) {
 200         offset = donor->offset; /* decrease left offset */
 201         merged = 1;
 202     }
 203
 204     /* do we have a right hand side overlap? */
 205     if (donor->offset <= rhs && rhs < donor_rhs) {
 206         rhs = donor_rhs;        /* increase right offset */
 207         merged = 1;
 208     }
 209
 210     /* adjust length if offsets have been changed */
 211     if (merged) {
 212         assert(rhs > offset);
 213         length = rhs - offset;
 214     } else {
 215         /* does recepient contain donor? */
 216         merged =
 217             offset <= donor->offset && donor->offset < rhs;
 218     }
 219
 220 #endif
 221     return merged;
 222 }
 223
 224 /*
 225  * Range
 226  */
 227
 228 HttpHdrRange::HttpHdrRange () : clen (HttpHdrRangeSpec::UnknownPosition)
 229 {}
 230
 231 HttpHdrRange *
 232 HttpHdrRange::ParseCreate(const String * range_spec)
 233 {
 234     HttpHdrRange *r = new HttpHdrRange;
 235
 236     if (!r->parseInit(range_spec)) {
 237         delete r;
 238         r = NULL;
 239     }
 240
 241     return r;
 242 }
 243
 244 /* returns true if ranges are valid; inits HttpHdrRange */
 245 bool
 246 HttpHdrRange::parseInit(const String * range_spec)
 247 {
 248     const char *item;
 249     const char *pos = NULL;
 250     int ilen;
 251     assert(this && range_spec);
 252     ++ParsedCount;
 253     debugs(64, 8, "parsing range field: '" << range_spec << "'");
 254     /* check range type */
 255
 256     if (range_spec->caseCmp("bytes=", 6))
 257         return 0;
 258
 259     /* skip "bytes="; hack! */
 260     pos = range_spec->termedBuf() + 6;
 261
 262     /* iterate through comma separated list */
 263     while (strListGetItem(range_spec, ',', &item, &ilen, &pos)) {
 264         HttpHdrRangeSpec *spec = HttpHdrRangeSpec::Create(item, ilen);
 265         /*
 266          * RFC 2616 section 14.35.1: MUST ignore Range with
 267          * at least one syntactically invalid byte-range-specs.
 268          */
 269         if (!spec) {
 270             while (!specs.empty())
 271                 delete specs.pop_back();
 272             debugs(64, 2, "ignoring invalid range field: '" << range_spec << "'");
 273             break;
 274         }
 275
 276         specs.push_back(spec);
 277     }
 278
 279     debugs(64, 8, "got range specs: " << specs.size());
 280     return !specs.empty();
 281 }
 282
 283 HttpHdrRange::~HttpHdrRange()
 284 {
 285     while (specs.size())
 286         delete specs.pop_back();
 287 }
 288
 289 HttpHdrRange::HttpHdrRange(HttpHdrRange const &old) : specs()
 290 {
 291     specs.reserve(old.specs.size());
 292
 293     for (const_iterator i = old.begin(); i != old.end(); ++i)
 294         specs.push_back(new HttpHdrRangeSpec ( **i));
 295
 296     assert(old.specs.size() == specs.size());
 297 }
 298
 299 HttpHdrRange::iterator
 300 HttpHdrRange::begin()
 301 {
 302     return specs.begin();
 303 }
 304
 305 HttpHdrRange::iterator
 306 HttpHdrRange::end()
 307 {
 308     return specs.end();
 309 }
 310
 311 HttpHdrRange::const_iterator
 312 HttpHdrRange::begin() const
 313 {
 314     return specs.begin();
 315 }
 316
 317 HttpHdrRange::const_iterator
 318 HttpHdrRange::end() const
 319 {
 320     return specs.end();
 321 }
 322
 323 void
 324 HttpHdrRange::packInto(Packer * packer) const
 325 {
 326     const_iterator pos = begin();
 327     assert(this);
 328
 329     while (pos != end()) {
 330         if (pos != begin())
 331             packerAppend(packer, ",", 1);
 332
 333         (*pos)->packInto(packer);
 334
 335         ++pos;
 336     }
 337 }
 338
 339 void
 340 HttpHdrRange::merge (Vector<HttpHdrRangeSpec *> &basis)
 341 {
 342     /* reset old array */
 343     specs.clean();
 344     /* merge specs:
 345      * take one spec from "goods" and merge it with specs from
 346      * "specs" (if any) until there is no overlap */
 347     iterator i = basis.begin();
 348
 349     while (i != basis.end()) {
 350         if (specs.size() && (*i)->mergeWith(specs.back())) {
 351             /* merged with current so get rid of the prev one */
 352             delete specs.pop_back();
 353             continue;   /* re-iterate */
 354         }
 355
 356         specs.push_back (*i);
 357         ++i;                    /* progress */
 358     }
 359
 360     debugs(64, 3, "HttpHdrRange::merge: had " << basis.size() <<
 361            " specs, merged " << basis.size() - specs.size() << " specs");
 362 }
 363
 364 void
 365 HttpHdrRange::getCanonizedSpecs (Vector<HttpHdrRangeSpec *> &copy)
 366 {
 367     /* canonize each entry and destroy bad ones if any */
 368
 369     for (iterator pos (begin()); pos != end(); ++pos) {
 370         if ((*pos)->canonize(clen))
 371             copy.push_back (*pos);
 372         else
 373             delete (*pos);
 374     }
 375
 376     debugs(64, 3, "HttpHdrRange::getCanonizedSpecs: found " <<
 377            specs.size() - copy.size() << " bad specs");
 378 }
 379
 380 #include "HttpHdrContRange.h"
 381
 382 /*
 383  * canonizes all range specs within a set preserving the order
 384  * returns true if the set is valid after canonization;
 385  * the set is valid if
 386  *   - all range specs are valid and
 387  *   - there is at least one range spec
 388  */
 389 int
 390 HttpHdrRange::canonize(HttpReply *rep)
 391 {
 392     assert(this && rep);
 393
 394     if (rep->content_range)
 395         clen = rep->content_range->elength;
 396     else
 397         clen = rep->content_length;
 398
 399     return canonize (clen);
 400 }
 401
 402 int
 403 HttpHdrRange::canonize (int64_t newClen)
 404 {
 405     clen = newClen;
 406     debugs(64, 3, "HttpHdrRange::canonize: started with " << specs.count <<
 407            " specs, clen: " << clen);
 408     Vector<HttpHdrRangeSpec*> goods;
 409     getCanonizedSpecs(goods);
 410     merge (goods);
 411     debugs(64, 3, "HttpHdrRange::canonize: finished with " << specs.count <<
 412            " specs");
 413     return specs.count > 0;
 414 }
 415
 416 /* hack: returns true if range specs are too "complex" for Squid to handle */
 417 /* requires that specs are "canonized" first! */
 418 bool
 419 HttpHdrRange::isComplex() const
 420 {
 421     int64_t offset = 0;
 422     assert(this);
 423     /* check that all rangers are in "strong" order */
 424     const_iterator pos (begin());
 425
 426     while (pos != end()) {
 427         /* Ensure typecasts is safe */
 428         assert ((*pos)->offset >= 0);
 429
 430         if ((*pos)->offset < offset)
 431             return 1;
 432
 433         offset = (*pos)->offset + (*pos)->length;
 434
 435         ++pos;
 436     }
 437
 438     return 0;
 439 }
 440
 441 /*
 442  * hack: returns true if range specs may be too "complex" when "canonized".
 443  * see also: HttpHdrRange::isComplex.
 444  */
 445 bool
 446 HttpHdrRange::willBeComplex() const
 447 {
 448     assert(this);
 449     /* check that all rangers are in "strong" order, */
 450     /* as far as we can tell without the content length */
 451     int64_t offset = 0;
 452
 453     for (const_iterator pos (begin()); pos != end(); ++pos) {
 454         if (!known_spec((*pos)->offset))        /* ignore unknowns */
 455             continue;
 456
 457         /* Ensure typecasts is safe */
 458         assert ((*pos)->offset >= 0);
 459
 460         if ((*pos)->offset < offset)
 461             return true;
 462
 463         offset = (*pos)->offset;
 464
 465         if (known_spec((*pos)->length)) /* avoid  unknowns */
 466             offset += (*pos)->length;
 467     }
 468
 469     return false;
 470 }
 471
 472 /*
 473  * Returns lowest known offset in range spec(s),
 474  * or HttpHdrRangeSpec::UnknownPosition
 475  * this is used for size limiting
 476  */
 477 int64_t
 478 HttpHdrRange::firstOffset() const
 479 {
 480     int64_t offset = HttpHdrRangeSpec::UnknownPosition;
 481     assert(this);
 482     const_iterator pos = begin();
 483
 484     while (pos != end()) {
 485         if ((*pos)->offset < offset || !known_spec(offset))
 486             offset = (*pos)->offset;
 487
 488         ++pos;
 489     }
 490
 491     return offset;
 492 }
 493
 494 /*
 495  * Returns lowest offset in range spec(s), 0 if unknown.
 496  * This is used for finding out where we need to start if all
 497  * ranges are combined into one, for example FTP REST.
 498  * Use 0 for size if unknown
 499  */
 500 int64_t
 501 HttpHdrRange::lowestOffset(int64_t size) const
 502 {
 503     int64_t offset = HttpHdrRangeSpec::UnknownPosition;
 504     const_iterator pos = begin();
 505     assert(this);
 506
 507     while (pos != end()) {
 508         int64_t current = (*pos)->offset;
 509
 510         if (!known_spec(current)) {
 511             if ((*pos)->length > size || !known_spec((*pos)->length))
 512                 return 0;       /* Unknown. Assume start of file */
 513
 514             current = size - (*pos)->length;
 515         }
 516
 517         if (current < offset || !known_spec(offset))
 518             offset = current;
 519
 520         ++pos;
 521     }
 522
 523     return known_spec(offset) ? offset : 0;
 524 }
 525
 526 /*
 527  * \retval true   Fetch only requested ranges. The first range is larger that configured limit.
 528  * \retval false  Full download. Not a range request, no limit, or the limit is not yet reached.
 529  */
 530 bool
 531 HttpHdrRange::offsetLimitExceeded(const int64_t limit) const
 532 {
 533     if (NULL == this)
 534         /* not a range request */
 535         return false;
 536
 537     if (limit == 0)
 538         /* 0 == disabled */
 539         return true;
 540
 541     if (-1 == limit)
 542         /* 'none' == forced */
 543         return false;
 544
 545     if (firstOffset() == -1)
 546         /* tail request */
 547         return true;
 548
 549     if (limit >= firstOffset())
 550         /* below the limit */
 551         return false;
 552
 553     return true;
 554 }
 555
 556 bool
 557 HttpHdrRange::contains(HttpHdrRangeSpec& r) const
 558 {
 559     assert(r.length >= 0);
 560     HttpHdrRangeSpec::HttpRange rrange(r.offset, r.offset + r.length);
 561
 562     for (const_iterator i = begin(); i != end(); ++i) {
 563         HttpHdrRangeSpec::HttpRange irange((*i)->offset, (*i)->offset + (*i)->length);
 564         HttpHdrRangeSpec::HttpRange intersection = rrange.intersection(irange);
 565
 566         if (intersection.start == irange.start && intersection.size() == irange.size())
 567             return true;
 568     }
 569
 570     return false;
 571 }
 572
 573 const HttpHdrRangeSpec *
 574 HttpHdrRangeIter::currentSpec() const
 575 {
 576     if (pos.incrementable())
 577         return *pos;
 578
 579     return NULL;
 580 }
 581
 582 void
 583 HttpHdrRangeIter::updateSpec()
 584 {
 585     assert (debt_size == 0);
 586     assert (valid);
 587
 588     if (pos.incrementable()) {
 589         debt(currentSpec()->length);
 590     }
 591 }
 592
 593 int64_t
 594 HttpHdrRangeIter::debt() const
 595 {
 596     debugs(64, 3, "HttpHdrRangeIter::debt: debt is " << debt_size);
 597     return debt_size;
 598 }
 599
 600 void HttpHdrRangeIter::debt(int64_t newDebt)
 601 {
 602     debugs(64, 3, "HttpHdrRangeIter::debt: was " << debt_size << " now " << newDebt);
 603     debt_size = newDebt;
 604 }