src/HttpHdrRange.cc

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