src/HttpHdrRange.cc

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