src/HttpHdrRange.cc

   1
   2 /*
   3  * $Id: HttpHdrRange.cc,v 1.29 2003/01/22 10:05:43 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
  39 /*
  40  *    Currently only byte ranges are supported
  41  *
  42  *    Essentially, there are three types of byte ranges:
  43  *
  44  *      1) first-byte-pos "-" last-byte-pos  // range
  45  *      2) first-byte-pos "-"                // trailer
  46  *      3)                "-" suffix-length  // suffix (last length bytes)
  47  *
  48  *
  49  *    When Range field is parsed, we have no clue about the content
  50  *    length of the document. Thus, we simply code an "absent" part
  51  *    using range_spec_unknown constant.
  52  *
  53  *    Note: when response length becomes known, we convert any range
  54  *    spec into type one above. (Canonization process).
  55  */
  56
  57
  58 /* local constants */
  59 #define range_spec_unknown ((ssize_t)-1)
  60
  61 /* local routines */
  62 #define known_spec(s) ((s) != range_spec_unknown)
  63 #define size_min(a,b) ((a) <= (b) ? (a) : (b))
  64 #define size_diff(a,b) ((a) >= (b) ? ((a)-(b)) : 0)
  65 static HttpHdrRangeSpec *httpHdrRangeSpecDup(const HttpHdrRangeSpec * spec);
  66 static int httpHdrRangeSpecCanonize(HttpHdrRangeSpec * spec, size_t clen);
  67 static void httpHdrRangeSpecPackInto(const HttpHdrRangeSpec * spec, Packer * p);
  68
  69 /* globals */
  70 static int RangeParsedCount = 0;
  71
  72 /*
  73  * Range-Spec
  74  */
  75
  76 static HttpHdrRangeSpec *
  77 httpHdrRangeSpecCreate(void)
  78 {
  79     return (HttpHdrRangeSpec *)memAllocate(MEM_HTTP_HDR_RANGE_SPEC);
  80 }
  81
  82 /* parses range-spec and returns new object on success */
  83 static HttpHdrRangeSpec *
  84 httpHdrRangeSpecParseCreate(const char *field, int flen)
  85 {
  86     HttpHdrRangeSpec spec =
  87     {range_spec_unknown, range_spec_unknown};
  88     const char *p;
  89     if (flen < 2)
  90         return NULL;
  91     /* is it a suffix-byte-range-spec ? */
  92     if (*field == '-') {
  93         if (!httpHeaderParseSize(field + 1, &spec.length))
  94             return NULL;
  95     } else
  96         /* must have a '-' somewhere in _this_ field */
  97     if (!((p = strchr(field, '-')) || (p - field >= flen))) {
  98         debug(64, 2) ("ignoring invalid (missing '-') range-spec near: '%s'\n", field);
  99         return NULL;
 100     } else {
 101         if (!httpHeaderParseSize(field, &spec.offset))
 102             return NULL;
 103         p++;
 104         /* do we have last-pos ? */
 105         if (p - field < flen) {
 106             ssize_t last_pos;
 107             if (!httpHeaderParseSize(p, &last_pos))
 108                 return NULL;
 109             spec.length = size_diff(last_pos + 1, spec.offset);
 110         }
 111     }
 112     /* we managed to parse, check if the result makes sence */
 113     if (known_spec(spec.length) && !spec.length) {
 114         debug(64, 2) ("ignoring invalid (zero length) range-spec near: '%s'\n", field);
 115         return NULL;
 116     }
 117     return httpHdrRangeSpecDup(&spec);
 118 }
 119
 120 static void
 121 httpHdrRangeSpecDestroy(HttpHdrRangeSpec * spec)
 122 {
 123     memFree(spec, MEM_HTTP_HDR_RANGE_SPEC);
 124 }
 125
 126
 127 static HttpHdrRangeSpec *
 128 httpHdrRangeSpecDup(const HttpHdrRangeSpec * spec)
 129 {
 130     HttpHdrRangeSpec *dup = httpHdrRangeSpecCreate();
 131     dup->offset = spec->offset;
 132     dup->length = spec->length;
 133     return dup;
 134 }
 135
 136 static void
 137 httpHdrRangeSpecPackInto(const HttpHdrRangeSpec * spec, Packer * p)
 138 {
 139     if (!known_spec(spec->offset))      /* suffix */
 140         packerPrintf(p, "-%ld", (long int) spec->length);
 141     else if (!known_spec(spec->length))         /* trailer */
 142         packerPrintf(p, "%ld-", (long int) spec->offset);
 143     else                        /* range */
 144         packerPrintf(p, "%ld-%ld",
 145             (long int) spec->offset, (long int) spec->offset + spec->length - 1);
 146 }
 147
 148 /* fills "absent" positions in range specification based on response body size
 149  * returns true if the range is still valid
 150  * range is valid if its intersection with [0,length-1] is not empty
 151  */
 152 static int
 153 httpHdrRangeSpecCanonize(HttpHdrRangeSpec * spec, size_t clen)
 154 {
 155     debug(64, 5) ("httpHdrRangeSpecCanonize: have: [%ld, %ld) len: %ld\n",
 156         (long int) spec->offset, (long int) spec->offset + spec->length, (long int) spec->length);
 157     /* ensure the type casts are safe */
 158     assert (spec->length >= 0);
 159     assert (spec->offset >= 0);
 160     if (!known_spec(spec->offset))      /* suffix */
 161         spec->offset = size_diff(clen, (size_t)spec->length);
 162     else if (!known_spec(spec->length))         /* trailer */
 163         spec->length = size_diff(clen, (size_t)spec->offset);
 164     /* we have a "range" now, adjust length if needed */
 165     assert(known_spec(spec->length));
 166     assert(known_spec(spec->offset));
 167     spec->length = size_min(size_diff(clen, (size_t)spec->offset), (size_t)spec->length);
 168     /* check range validity */
 169     debug(64, 5) ("httpHdrRangeSpecCanonize: done: [%ld, %ld) len: %ld\n",
 170         (long int) spec->offset, (long int) spec->offset + (long int) spec->length, (long int) spec->length);
 171     return spec->length > 0;
 172 }
 173
 174 /* merges recepient with donor if possible; returns true on success
 175  * both specs must be canonized prior to merger, of course */
 176 static int
 177 httpHdrRangeSpecMergeWith(HttpHdrRangeSpec * recep, const HttpHdrRangeSpec * donor)
 178 {
 179     int merged = 0;
 180 #if MERGING_BREAKS_NOTHING
 181     /* Note: this code works, but some clients may not like its effects */
 182     size_t rhs = recep->offset + recep->length;         /* no -1 ! */
 183     const size_t donor_rhs = donor->offset + donor->length;     /* no -1 ! */
 184     assert(known_spec(recep->offset));
 185     assert(known_spec(donor->offset));
 186     assert(recep->length > 0);
 187     assert(donor->length > 0);
 188     /* do we have a left hand side overlap? */
 189     if (donor->offset < recep->offset && recep->offset <= donor_rhs) {
 190         recep->offset = donor->offset;  /* decrease left offset */
 191         merged = 1;
 192     }
 193     /* do we have a right hand side overlap? */
 194     if (donor->offset <= rhs && rhs < donor_rhs) {
 195         rhs = donor_rhs;        /* increase right offset */
 196         merged = 1;
 197     }
 198     /* adjust length if offsets have been changed */
 199     if (merged) {
 200         assert(rhs > recep->offset);
 201         recep->length = rhs - recep->offset;
 202     } else {
 203         /* does recepient contain donor? */
 204         merged =
 205             recep->offset <= donor->offset && donor->offset < rhs;
 206     }
 207 #endif
 208     return merged;
 209 }
 210
 211 /*
 212  * Range
 213  */
 214
 215 static HttpHdrRange *
 216 httpHdrRangeCreate(void)
 217 {
 218     HttpHdrRange *r = (HttpHdrRange *)memAllocate(MEM_HTTP_HDR_RANGE);
 219     stackInit(&r->specs);
 220     return r;
 221 }
 222
 223 HttpHdrRange *
 224 httpHdrRangeParseCreate(const String * str)
 225 {
 226     HttpHdrRange *r = httpHdrRangeCreate();
 227     if (!httpHdrRangeParseInit(r, str)) {
 228         httpHdrRangeDestroy(r);
 229         r = NULL;
 230     }
 231     return r;
 232 }
 233
 234 /* returns true if ranges are valid; inits HttpHdrRange */
 235 int
 236 httpHdrRangeParseInit(HttpHdrRange * range, const String * str)
 237 {
 238     const char *item;
 239     const char *pos = NULL;
 240     int ilen;
 241     int count = 0;
 242     assert(range && str);
 243     RangeParsedCount++;
 244     debug(64, 8) ("parsing range field: '%s'\n", strBuf(*str));
 245     /* check range type */
 246     if (strNCaseCmp(*str, "bytes=", 6))
 247         return 0;
 248     /* skip "bytes="; hack! */
 249     pos = strBuf(*str) + 5;
 250     /* iterate through comma separated list */
 251     while (strListGetItem(str, ',', &item, &ilen, &pos)) {
 252         HttpHdrRangeSpec *spec = httpHdrRangeSpecParseCreate(item, ilen);
 253         /*
 254          * HTTP/1.1 draft says we must ignore the whole header field if one spec
 255          * is invalid. However, RFC 2068 just says that we must ignore that spec.
 256          */
 257         if (spec)
 258             stackPush(&range->specs, spec);
 259         count++;
 260     }
 261     debug(64, 8) ("parsed range range count: %d\n", range->specs.count);
 262     return range->specs.count;
 263 }
 264
 265 void
 266 httpHdrRangeDestroy(HttpHdrRange * range)
 267 {
 268     assert(range);
 269     while (range->specs.count)
 270         httpHdrRangeSpecDestroy((HttpHdrRangeSpec *)stackPop(&range->specs));
 271     stackClean(&range->specs);
 272     memFree(range, MEM_HTTP_HDR_RANGE);
 273 }
 274
 275 HttpHdrRange *
 276 httpHdrRangeDup(const HttpHdrRange * range)
 277 {
 278     HttpHdrRange *dup;
 279     size_t i;
 280     assert(range);
 281     dup = httpHdrRangeCreate();
 282     stackPrePush(&dup->specs, range->specs.count);
 283     for (i = 0; i < range->specs.count; i++)
 284         stackPush(&dup->specs, httpHdrRangeSpecDup((HttpHdrRangeSpec *)range->specs.items[i]));
 285     assert(range->specs.count == dup->specs.count);
 286     return dup;
 287 }
 288
 289 void
 290 httpHdrRangePackInto(const HttpHdrRange * range, Packer * p)
 291 {
 292     HttpHdrRangePos pos = HttpHdrRangeInitPos;
 293     const HttpHdrRangeSpec *spec;
 294     assert(range);
 295     while ((spec = httpHdrRangeGetSpec(range, &pos))) {
 296         if (pos != HttpHdrRangeInitPos)
 297             packerAppend(p, ",", 1);
 298         httpHdrRangeSpecPackInto(spec, p);
 299     }
 300 }
 301
 302 /*
 303  * canonizes all range specs within a set preserving the order
 304  * returns true if the set is valid after canonization;
 305  * the set is valid if
 306  *   - all range specs are valid and
 307  *   - there is at least one range spec
 308  */
 309 int
 310 httpHdrRangeCanonize(HttpHdrRange * range, ssize_t clen)
 311 {
 312     size_t i;
 313     HttpHdrRangeSpec *spec;
 314     HttpHdrRangePos pos = HttpHdrRangeInitPos;
 315     Stack goods;
 316     assert(range);
 317     assert(clen >= 0);
 318     stackInit(&goods);
 319     debug(64, 3) ("httpHdrRangeCanonize: started with %d specs, clen: %ld\n", range->specs.count, (long int) clen);
 320
 321     /* canonize each entry and destroy bad ones if any */
 322     while ((spec = httpHdrRangeGetSpec(range, &pos))) {
 323         if (httpHdrRangeSpecCanonize(spec, clen))
 324             stackPush(&goods, spec);
 325         else
 326             httpHdrRangeSpecDestroy(spec);
 327     }
 328     debug(64, 3) ("httpHdrRangeCanonize: found %d bad specs\n",
 329         range->specs.count - goods.count);
 330     /* reset old array */
 331     stackClean(&range->specs);
 332     stackInit(&range->specs);
 333     spec = NULL;
 334     /* merge specs:
 335      * take one spec from "goods" and merge it with specs from
 336      * "range->specs" (if any) until there is no overlap */
 337     for (i = 0; i < goods.count;) {
 338         HttpHdrRangeSpec *prev_spec = (HttpHdrRangeSpec *)stackTop(&range->specs);
 339         spec = (HttpHdrRangeSpec *)goods.items[i];
 340         if (prev_spec) {
 341             if (httpHdrRangeSpecMergeWith(spec, prev_spec)) {
 342                 /* merged with current so get rid of the prev one */
 343                 assert(prev_spec == stackPop(&range->specs));
 344                 httpHdrRangeSpecDestroy(prev_spec);
 345                 continue;       /* re-iterate */
 346             }
 347         }
 348         stackPush(&range->specs, spec);
 349         spec = NULL;
 350         i++;                    /* progress */
 351     }
 352     if (spec)                   /* last "merge" may not be pushed yet */
 353         stackPush(&range->specs, spec);
 354     debug(64, 3) ("httpHdrRangeCanonize: had %d specs, merged %d specs\n",
 355         goods.count, goods.count - range->specs.count);
 356     debug(64, 3) ("httpHdrRangeCanonize: finished with %d specs\n",
 357         range->specs.count);
 358     stackClean(&goods);
 359     return range->specs.count > 0;
 360 }
 361
 362 /* searches for next range, returns true if found */
 363 HttpHdrRangeSpec *
 364 httpHdrRangeGetSpec(const HttpHdrRange * range, HttpHdrRangePos * pos)
 365 {
 366     assert(range);
 367     assert(pos && *pos >= -1 && *pos < (ssize_t)range->specs.count);
 368     (*pos)++;
 369     if (*pos < (ssize_t)range->specs.count)
 370         return (HttpHdrRangeSpec *) range->specs.items[*pos];
 371     else
 372         return NULL;
 373 }
 374
 375 /* hack: returns true if range specs are too "complex" for Squid to handle */
 376 /* requires that specs are "canonized" first! */
 377 int
 378 httpHdrRangeIsComplex(const HttpHdrRange * range)
 379 {
 380     HttpHdrRangePos pos = HttpHdrRangeInitPos;
 381     const HttpHdrRangeSpec *spec;
 382     size_t offset = 0;
 383     assert(range);
 384     /* check that all rangers are in "strong" order */
 385     while ((spec = httpHdrRangeGetSpec(range, &pos))) {
 386         /* Ensure typecasts is safe */
 387         assert (spec->offset >= 0);
 388         if ((unsigned int)spec->offset < offset)
 389             return 1;
 390         offset = spec->offset + spec->length;
 391     }
 392     return 0;
 393 }
 394
 395 /*
 396  * hack: returns true if range specs may be too "complex" when "canonized".
 397  * see also: httpHdrRangeIsComplex.
 398  */
 399 int
 400 httpHdrRangeWillBeComplex(const HttpHdrRange * range)
 401 {
 402     HttpHdrRangePos pos = HttpHdrRangeInitPos;
 403     const HttpHdrRangeSpec *spec;
 404     size_t offset = 0;
 405     assert(range);
 406     /* check that all rangers are in "strong" order, */
 407     /* as far as we can tell without the content length */
 408     while ((spec = httpHdrRangeGetSpec(range, &pos))) {
 409         if (!known_spec(spec->offset))  /* ignore unknowns */
 410             continue;
 411         /* Ensure typecasts is safe */
 412         assert (spec->offset >= 0);
 413         if ((size_t) spec->offset < offset)
 414             return 1;
 415         offset = spec->offset;
 416         if (known_spec(spec->length))   /* avoid  unknowns */
 417             offset += spec->length;
 418     }
 419     return 0;
 420 }
 421
 422 /*
 423  * Returns lowest known offset in range spec(s), or range_spec_unknown
 424  * this is used for size limiting
 425  */
 426 ssize_t
 427 httpHdrRangeFirstOffset(const HttpHdrRange * range)
 428 {
 429     ssize_t offset = range_spec_unknown;
 430     HttpHdrRangePos pos = HttpHdrRangeInitPos;
 431     const HttpHdrRangeSpec *spec;
 432     assert(range);
 433     while ((spec = httpHdrRangeGetSpec(range, &pos))) {
 434         if (spec->offset < offset || !known_spec(offset))
 435             offset = spec->offset;
 436     }
 437     return offset;
 438 }
 439
 440 /*
 441  * Returns lowest offset in range spec(s), 0 if unknown.
 442  * This is used for finding out where we need to start if all
 443  * ranges are combined into one, for example FTP REST.
 444  * Use 0 for size if unknown
 445  */
 446 ssize_t
 447 httpHdrRangeLowestOffset(const HttpHdrRange * range, ssize_t size)
 448 {
 449     ssize_t offset = range_spec_unknown;
 450     ssize_t current;
 451     HttpHdrRangePos pos = HttpHdrRangeInitPos;
 452     const HttpHdrRangeSpec *spec;
 453     assert(range);
 454     while ((spec = httpHdrRangeGetSpec(range, &pos))) {
 455         current = spec->offset;
 456         if (!known_spec(current)) {
 457             if (spec->length > size || !known_spec(spec->length))
 458                 return 0;       /* Unknown. Assume start of file */
 459             current = size - spec->length;
 460         }
 461         if (current < offset || !known_spec(offset))
 462             offset = current;
 463     }
 464     return known_spec(offset) ? offset : 0;
 465 }
 466
 467 /* generates a "unique" boundary string for multipart responses
 468  * the caller is responsible for cleaning the string */
 469 String
 470 httpHdrRangeBoundaryStr(clientHttpRequest * http)
 471 {
 472     const char *key;
 473     String b = StringNull;
 474     assert(http);
 475     stringAppend(&b, full_appname_string, strlen(full_appname_string));
 476     stringAppend(&b, ":", 1);
 477     key = http->entry->getMD5Text();
 478     stringAppend(&b, key, strlen(key));
 479     return b;
 480 }
 481
 482 /*
 483  * Return true if the first range offset is larger than the configured
 484  * limit.
 485  */
 486 int
 487 httpHdrRangeOffsetLimit(HttpHdrRange * range)
 488 {
 489     if (NULL == range)
 490         /* not a range request */
 491         return 0;
 492     if (-1 == (ssize_t)Config.rangeOffsetLimit)
 493         /* disabled */
 494         return 0;
 495     if ((ssize_t)Config.rangeOffsetLimit >= httpHdrRangeFirstOffset(range))
 496         /* below the limit */
 497         return 0;
 498     return 1;
 499 }