src/HttpHdrRange.cc

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