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 #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(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(Packable * packer) const
 307 {
 308     const_iterator pos = begin();
 309
 310     while (pos != end()) {
 311         if (pos != begin())
 312             packer->append(",", 1);
 313
 314         (*pos)->packInto(packer);
 315
 316         ++pos;
 317     }
 318 }
 319
 320 void
 321 HttpHdrRange::merge (std::vector<HttpHdrRangeSpec *> &basis)
 322 {
 323     /* reset old array */
 324     specs.clear();
 325     /* merge specs:
 326      * take one spec from "goods" and merge it with specs from
 327      * "specs" (if any) until there is no overlap */
 328     iterator i = basis.begin();
 329
 330     while (i != basis.end()) {
 331         if (specs.size() && (*i)->mergeWith(specs.back())) {
 332             /* merged with current so get rid of the prev one */
 333             delete specs.back();
 334             specs.pop_back();
 335             continue;   /* re-iterate */
 336         }
 337
 338         specs.push_back (*i);
 339         ++i;            /* progress */
 340     }
 341
 342     debugs(64, 3, "HttpHdrRange::merge: had " << basis.size() <<
 343            " specs, merged " << basis.size() - specs.size() << " specs");
 344 }
 345
 346 void
 347 HttpHdrRange::getCanonizedSpecs(std::vector<HttpHdrRangeSpec *> &copy)
 348 {
 349     /* canonize each entry and destroy bad ones if any */
 350
 351     for (iterator pos (begin()); pos != end(); ++pos) {
 352         if ((*pos)->canonize(clen))
 353             copy.push_back (*pos);
 354         else
 355             delete (*pos);
 356     }
 357
 358     debugs(64, 3, "found " << specs.size() - copy.size() << " bad specs");
 359 }
 360
 361 #include "HttpHdrContRange.h"
 362
 363 /*
 364  * canonizes all range specs within a set preserving the order
 365  * returns true if the set is valid after canonization;
 366  * the set is valid if
 367  *   - all range specs are valid and
 368  *   - there is at least one range spec
 369  */
 370 int
 371 HttpHdrRange::canonize(HttpReply *rep)
 372 {
 373     assert(rep);
 374
 375     if (rep->contentRange())
 376         clen = rep->contentRange()->elength;
 377     else
 378         clen = rep->content_length;
 379
 380     return canonize (clen);
 381 }
 382
 383 int
 384 HttpHdrRange::canonize (int64_t newClen)
 385 {
 386     clen = newClen;
 387     debugs(64, 3, "HttpHdrRange::canonize: started with " << specs.size() <<
 388            " specs, clen: " << clen);
 389     std::vector<HttpHdrRangeSpec*> goods;
 390     getCanonizedSpecs(goods);
 391     merge (goods);
 392     debugs(64, 3, "HttpHdrRange::canonize: finished with " << specs.size() <<
 393            " specs");
 394     return specs.size() > 0; // TODO: should return bool
 395 }
 396
 397 /* hack: returns true if range specs are too "complex" for Squid to handle */
 398 /* requires that specs are "canonized" first! */
 399 bool
 400 HttpHdrRange::isComplex() const
 401 {
 402     int64_t offset = 0;
 403     /* check that all rangers are in "strong" order */
 404     const_iterator pos (begin());
 405
 406     while (pos != end()) {
 407         /* Ensure typecasts is safe */
 408         assert ((*pos)->offset >= 0);
 409
 410         if ((*pos)->offset < offset)
 411             return 1;
 412
 413         offset = (*pos)->offset + (*pos)->length;
 414
 415         ++pos;
 416     }
 417
 418     return 0;
 419 }
 420
 421 /*
 422  * hack: returns true if range specs may be too "complex" when "canonized".
 423  * see also: HttpHdrRange::isComplex.
 424  */
 425 bool
 426 HttpHdrRange::willBeComplex() const
 427 {
 428     /* check that all rangers are in "strong" order, */
 429     /* as far as we can tell without the content length */
 430     int64_t offset = 0;
 431
 432     for (const_iterator pos (begin()); pos != end(); ++pos) {
 433         if (!known_spec((*pos)->offset))    /* ignore unknowns */
 434             continue;
 435
 436         /* Ensure typecasts is safe */
 437         assert ((*pos)->offset >= 0);
 438
 439         if ((*pos)->offset < offset)
 440             return true;
 441
 442         offset = (*pos)->offset;
 443
 444         if (known_spec((*pos)->length)) /* avoid  unknowns */
 445             offset += (*pos)->length;
 446     }
 447
 448     return false;
 449 }
 450
 451 /*
 452  * Returns lowest known offset in range spec(s),
 453  * or HttpHdrRangeSpec::UnknownPosition
 454  * this is used for size limiting
 455  */
 456 int64_t
 457 HttpHdrRange::firstOffset() const
 458 {
 459     int64_t offset = HttpHdrRangeSpec::UnknownPosition;
 460     const_iterator pos = begin();
 461
 462     while (pos != end()) {
 463         if ((*pos)->offset < offset || !known_spec(offset))
 464             offset = (*pos)->offset;
 465
 466         ++pos;
 467     }
 468
 469     return offset;
 470 }
 471
 472 /*
 473  * Returns lowest offset in range spec(s), 0 if unknown.
 474  * This is used for finding out where we need to start if all
 475  * ranges are combined into one, for example FTP REST.
 476  * Use 0 for size if unknown
 477  */
 478 int64_t
 479 HttpHdrRange::lowestOffset(int64_t size) const
 480 {
 481     int64_t offset = HttpHdrRangeSpec::UnknownPosition;
 482     const_iterator pos = begin();
 483
 484     while (pos != end()) {
 485         int64_t current = (*pos)->offset;
 486
 487         if (!known_spec(current)) {
 488             if ((*pos)->length > size || !known_spec((*pos)->length))
 489                 return 0;   /* Unknown. Assume start of file */
 490
 491             current = size - (*pos)->length;
 492         }
 493
 494         if (current < offset || !known_spec(offset))
 495             offset = current;
 496
 497         ++pos;
 498     }
 499
 500     return known_spec(offset) ? offset : 0;
 501 }
 502
 503 /*
 504  * \retval true   Fetch only requested ranges. The first range is larger that configured limit.
 505  * \retval false  Full download. Not a range request, no limit, or the limit is not yet reached.
 506  */
 507 bool
 508 HttpHdrRange::offsetLimitExceeded(const int64_t limit) const
 509 {
 510     if (limit == 0)
 511         /* 0 == disabled */
 512         return true;
 513
 514     if (-1 == limit)
 515         /* 'none' == forced */
 516         return false;
 517
 518     if (firstOffset() == -1)
 519         /* tail request */
 520         return true;
 521
 522     if (limit >= firstOffset())
 523         /* below the limit */
 524         return false;
 525
 526     return true;
 527 }
 528
 529 const HttpHdrRangeSpec *
 530 HttpHdrRangeIter::currentSpec() const
 531 {
 532     if (pos != end)
 533         return *pos;
 534
 535     return NULL;
 536 }
 537
 538 void
 539 HttpHdrRangeIter::updateSpec()
 540 {
 541     assert (debt_size == 0);
 542     assert (valid);
 543
 544     if (pos != end) {
 545         debt(currentSpec()->length);
 546     }
 547 }
 548
 549 int64_t
 550 HttpHdrRangeIter::debt() const
 551 {
 552     debugs(64, 3, "HttpHdrRangeIter::debt: debt is " << debt_size);
 553     return debt_size;
 554 }
 555
 556 void HttpHdrRangeIter::debt(int64_t newDebt)
 557 {
 558     debugs(64, 3, "HttpHdrRangeIter::debt: was " << debt_size << " now " << newDebt);
 559     debt_size = newDebt;
 560 }
 561