src/HttpHdrRange.cc

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