src/HttpHdrRange.cc

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