src/HttpHdrRange.cc

   1 /*
   2  * Copyright (C) 1996-2021 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 "http/Stream.h"
  14 #include "HttpHeaderRange.h"
  15 #include "HttpHeaderTools.h"
  16 #include "HttpReply.h"
  17 #include "Store.h"
  18 #include "StrList.h"
  19
  20 /*
  21  *    Currently only byte ranges are supported
  22  *
  23  *    Essentially, there are three types of byte ranges:
  24  *
  25  *      1) first-byte-pos "-" last-byte-pos  // range
  26  *      2) first-byte-pos "-"                // trailer
  27  *      3)                "-" suffix-length  // suffix (last length bytes)
  28  *
  29  *
  30  *    When Range field is parsed, we have no clue about the content
  31  *    length of the document. Thus, we simply code an "absent" part
  32  *    using HttpHdrRangeSpec::UnknownPosition constant.
  33  *
  34  *    Note: when response length becomes known, we convert any range
  35  *    spec into type one above. (Canonization process).
  36  */
  37
  38 /* local routines */
  39 #define known_spec(s) ((s) > HttpHdrRangeSpec::UnknownPosition)
  40
  41 /* globals */
  42 size_t HttpHdrRange::ParsedCount = 0;
  43 int64_t const HttpHdrRangeSpec::UnknownPosition = -1;
  44
  45 /*
  46  * Range-Spec
  47  */
  48
  49 HttpHdrRangeSpec::HttpHdrRangeSpec() : offset(UnknownPosition), length(UnknownPosition) {}
  50
  51 /* parses range-spec and returns new object on success */
  52 HttpHdrRangeSpec *
  53 HttpHdrRangeSpec::Create(const char *field, int flen)
  54 {
  55     HttpHdrRangeSpec spec;
  56
  57     if (!spec.parseInit(field, flen))
  58         return NULL;
  59
  60     return new HttpHdrRangeSpec(spec);
  61 }
  62
  63 bool
  64 HttpHdrRangeSpec::parseInit(const char *field, int flen)
  65 {
  66     const char *p;
  67
  68     if (flen < 2)
  69         return false;
  70
  71     /* is it a suffix-byte-range-spec ? */
  72     if (*field == '-') {
  73         if (!httpHeaderParseOffset(field + 1, &length) || !known_spec(length))
  74             return false;
  75     } else
  76         /* must have a '-' somewhere in _this_ field */
  77         if (!((p = strchr(field, '-')) && (p - field < flen))) {
  78             debugs(64, 2, "invalid (missing '-') range-spec near: '" << field << "'");
  79             return false;
  80         } else {
  81             if (!httpHeaderParseOffset(field, &offset) || !known_spec(offset))
  82                 return false;
  83
  84             ++p;
  85
  86             /* do we have last-pos ? */
  87             if (p - field < flen) {
  88                 int64_t last_pos;
  89
  90                 if (!httpHeaderParseOffset(p, &last_pos) || !known_spec(last_pos))
  91                     return false;
  92
  93                 // RFC 2616 s14.35.1 MUST: last-byte-pos >= first-byte-pos
  94                 if (last_pos < offset) {
  95                     debugs(64, 2, "invalid (last-byte-pos < first-byte-pos) range-spec near: " << field);
  96                     return false;
  97                 }
  98
  99                 HttpHdrRangeSpec::HttpRange aSpec (offset, last_pos + 1);
 100
 101                 length = aSpec.size();
 102             }
 103         }
 104
 105     return true;
 106 }
 107
 108 void
 109 HttpHdrRangeSpec::packInto(Packable * p) const
 110 {
 111     if (!known_spec(offset))    /* suffix */
 112         p->appendf("-%" PRId64, length);
 113     else if (!known_spec(length))       /* trailer */
 114         p->appendf("%" PRId64 "-", offset);
 115     else            /* range */
 116         p->appendf("%" PRId64 "-%" PRId64, 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 recipient 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 recipient contain donor? */
 192         merged =
 193             offset <= donor->offset && donor->offset < rhs;
 194     }
 195
 196 #else
 197     (void)donor;
 198 #endif
 199     return merged;
 200 }
 201
 202 /*
 203  * Range
 204  */
 205
 206 HttpHdrRange::HttpHdrRange() : clen(HttpHdrRangeSpec::UnknownPosition)
 207 {}
 208
 209 HttpHdrRange *
 210 HttpHdrRange::ParseCreate(const String * range_spec)
 211 {
 212     HttpHdrRange *r = new HttpHdrRange;
 213
 214     if (!r->parseInit(range_spec)) {
 215         delete r;
 216         r = NULL;
 217     }
 218
 219     return r;
 220 }
 221
 222 /* returns true if ranges are valid; inits HttpHdrRange */
 223 bool
 224 HttpHdrRange::parseInit(const String * range_spec)
 225 {
 226     const char *item;
 227     const char *pos = NULL;
 228     int ilen;
 229     assert(range_spec);
 230     ++ParsedCount;
 231     debugs(64, 8, "parsing range field: '" << *range_spec << "'");
 232     /* check range type */
 233
 234     if (range_spec->caseCmp("bytes=", 6))
 235         return 0;
 236
 237     /* skip "bytes="; hack! */
 238     pos = range_spec->termedBuf() + 6;
 239
 240     /* iterate through comma separated list */
 241     while (strListGetItem(range_spec, ',', &item, &ilen, &pos)) {
 242         HttpHdrRangeSpec *spec = HttpHdrRangeSpec::Create(item, ilen);
 243         /*
 244          * RFC 2616 section 14.35.1: MUST ignore Range with
 245          * at least one syntactically invalid byte-range-specs.
 246          */
 247         if (!spec) {
 248             while (!specs.empty()) {
 249                 delete specs.back();
 250                 specs.pop_back();
 251             }
 252             debugs(64, 2, "ignoring invalid range field: '" << *range_spec << "'");
 253             break;
 254         }
 255
 256         specs.push_back(spec);
 257     }
 258
 259     debugs(64, 8, "got range specs: " << specs.size());
 260     return !specs.empty();
 261 }
 262
 263 HttpHdrRange::~HttpHdrRange()
 264 {
 265     while (!specs.empty()) {
 266         delete specs.back();
 267         specs.pop_back();
 268     }
 269 }
 270
 271 HttpHdrRange::HttpHdrRange(HttpHdrRange const &old) :
 272     specs(),
 273     clen(HttpHdrRangeSpec::UnknownPosition)
 274 {
 275     specs.reserve(old.specs.size());
 276
 277     for (const_iterator i = old.begin(); i != old.end(); ++i)
 278         specs.push_back(new HttpHdrRangeSpec ( **i));
 279
 280     assert(old.specs.size() == specs.size());
 281 }
 282
 283 HttpHdrRange::iterator
 284 HttpHdrRange::begin()
 285 {
 286     return specs.begin();
 287 }
 288
 289 HttpHdrRange::iterator
 290 HttpHdrRange::end()
 291 {
 292     return specs.end();
 293 }
 294
 295 HttpHdrRange::const_iterator
 296 HttpHdrRange::begin() const
 297 {
 298     return specs.begin();
 299 }
 300
 301 HttpHdrRange::const_iterator
 302 HttpHdrRange::end() const
 303 {
 304     return specs.end();
 305 }
 306
 307 void
 308 HttpHdrRange::packInto(Packable * packer) const
 309 {
 310     const_iterator pos = begin();
 311
 312     while (pos != end()) {
 313         if (pos != begin())
 314             packer->append(",", 1);
 315
 316         (*pos)->packInto(packer);
 317
 318         ++pos;
 319     }
 320 }
 321
 322 void
 323 HttpHdrRange::merge (std::vector<HttpHdrRangeSpec *> &basis)
 324 {
 325     /* reset old array */
 326     specs.clear();
 327     /* merge specs:
 328      * take one spec from "goods" and merge it with specs from
 329      * "specs" (if any) until there is no overlap */
 330     iterator i = basis.begin();
 331
 332     while (i != basis.end()) {
 333         if (specs.size() && (*i)->mergeWith(specs.back())) {
 334             /* merged with current so get rid of the prev one */
 335             delete specs.back();
 336             specs.pop_back();
 337             continue;   /* re-iterate */
 338         }
 339
 340         specs.push_back (*i);
 341         ++i;            /* progress */
 342     }
 343
 344     debugs(64, 3, "HttpHdrRange::merge: had " << basis.size() <<
 345            " specs, merged " << basis.size() - specs.size() << " specs");
 346 }
 347
 348 void
 349 HttpHdrRange::getCanonizedSpecs(std::vector<HttpHdrRangeSpec *> &copy)
 350 {
 351     /* canonize each entry and destroy bad ones if any */
 352
 353     for (iterator pos (begin()); pos != end(); ++pos) {
 354         if ((*pos)->canonize(clen))
 355             copy.push_back (*pos);
 356         else
 357             delete (*pos);
 358     }
 359
 360     debugs(64, 3, "found " << specs.size() - copy.size() << " bad specs");
 361 }
 362
 363 #include "HttpHdrContRange.h"
 364
 365 /*
 366  * canonizes all range specs within a set preserving the order
 367  * returns true if the set is valid after canonization;
 368  * the set is valid if
 369  *   - all range specs are valid and
 370  *   - there is at least one range spec
 371  */
 372 int
 373 HttpHdrRange::canonize(HttpReply *rep)
 374 {
 375     assert(rep);
 376
 377     if (rep->contentRange())
 378         clen = rep->contentRange()->elength;
 379     else
 380         clen = rep->content_length;
 381
 382     return canonize (clen);
 383 }
 384
 385 int
 386 HttpHdrRange::canonize (int64_t newClen)
 387 {
 388     clen = newClen;
 389     debugs(64, 3, "HttpHdrRange::canonize: started with " << specs.size() <<
 390            " specs, clen: " << clen);
 391     std::vector<HttpHdrRangeSpec*> goods;
 392     getCanonizedSpecs(goods);
 393     merge (goods);
 394     debugs(64, 3, "HttpHdrRange::canonize: finished with " << specs.size() <<
 395            " specs");
 396     return specs.size() > 0; // TODO: should return bool
 397 }
 398
 399 /* hack: returns true if range specs are too "complex" for Squid to handle */
 400 /* requires that specs are "canonized" first! */
 401 bool
 402 HttpHdrRange::isComplex() const
 403 {
 404     int64_t offset = 0;
 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     /* check that all rangers are in "strong" order, */
 431     /* as far as we can tell without the content length */
 432     int64_t offset = 0;
 433
 434     for (const_iterator pos (begin()); pos != end(); ++pos) {
 435         if (!known_spec((*pos)->offset))    /* ignore unknowns */
 436             continue;
 437
 438         /* Ensure typecasts is safe */
 439         assert ((*pos)->offset >= 0);
 440
 441         if ((*pos)->offset < offset)
 442             return true;
 443
 444         offset = (*pos)->offset;
 445
 446         if (known_spec((*pos)->length)) /* avoid  unknowns */
 447             offset += (*pos)->length;
 448     }
 449
 450     return false;
 451 }
 452
 453 /*
 454  * Returns lowest known offset in range spec(s),
 455  * or HttpHdrRangeSpec::UnknownPosition
 456  * this is used for size limiting
 457  */
 458 int64_t
 459 HttpHdrRange::firstOffset() const
 460 {
 461     int64_t offset = HttpHdrRangeSpec::UnknownPosition;
 462     const_iterator pos = begin();
 463
 464     while (pos != end()) {
 465         if ((*pos)->offset < offset || !known_spec(offset))
 466             offset = (*pos)->offset;
 467
 468         ++pos;
 469     }
 470
 471     return offset;
 472 }
 473
 474 /*
 475  * Returns lowest offset in range spec(s), 0 if unknown.
 476  * This is used for finding out where we need to start if all
 477  * ranges are combined into one, for example FTP REST.
 478  * Use 0 for size if unknown
 479  */
 480 int64_t
 481 HttpHdrRange::lowestOffset(int64_t size) const
 482 {
 483     int64_t offset = HttpHdrRangeSpec::UnknownPosition;
 484     const_iterator pos = begin();
 485
 486     while (pos != end()) {
 487         int64_t current = (*pos)->offset;
 488
 489         if (!known_spec(current)) {
 490             if ((*pos)->length > size || !known_spec((*pos)->length))
 491                 return 0;   /* Unknown. Assume start of file */
 492
 493             current = size - (*pos)->length;
 494         }
 495
 496         if (current < offset || !known_spec(offset))
 497             offset = current;
 498
 499         ++pos;
 500     }
 501
 502     return known_spec(offset) ? offset : 0;
 503 }
 504
 505 /*
 506  * \retval true   Fetch only requested ranges. The first range is larger that configured limit.
 507  * \retval false  Full download. Not a range request, no limit, or the limit is not yet reached.
 508  */
 509 bool
 510 HttpHdrRange::offsetLimitExceeded(const int64_t limit) const
 511 {
 512     if (limit == 0)
 513         /* 0 == disabled */
 514         return true;
 515
 516     if (-1 == limit)
 517         /* 'none' == forced */
 518         return false;
 519
 520     if (firstOffset() == -1)
 521         /* tail request */
 522         return true;
 523
 524     if (limit >= firstOffset())
 525         /* below the limit */
 526         return false;
 527
 528     return true;
 529 }
 530
 531 const HttpHdrRangeSpec *
 532 HttpHdrRangeIter::currentSpec() const
 533 {
 534     if (pos != end)
 535         return *pos;
 536
 537     return NULL;
 538 }
 539
 540 void
 541 HttpHdrRangeIter::updateSpec()
 542 {
 543     assert (debt_size == 0);
 544     assert (valid);
 545
 546     if (pos != end) {
 547         debt(currentSpec()->length);
 548     }
 549 }
 550
 551 int64_t
 552 HttpHdrRangeIter::debt() const
 553 {
 554     debugs(64, 3, "HttpHdrRangeIter::debt: debt is " << debt_size);
 555     return debt_size;
 556 }
 557
 558 void HttpHdrRangeIter::debt(int64_t newDebt)
 559 {
 560     debugs(64, 3, "HttpHdrRangeIter::debt: was " << debt_size << " now " << newDebt);
 561     debt_size = newDebt;
 562 }
 563