src/HttpHdrRange.cc

   1
   2 /*
   3  * $Id: HttpHdrRange.cc,v 1.10 1998/06/04 20:25:03 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
  14  *  the National Science Foundation.
  15  *
  16  *  This program is free software; you can redistribute it and/or modify
  17  *  it under the terms of the GNU General Public License as published by
  18  *  the Free Software Foundation; either version 2 of the License, or
  19  *  (at your option) any later version.
  20  *
  21  *  This program is distributed in the hope that it will be useful,
  22  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  23  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  24  *  GNU General Public License for more details.
  25  *
  26  *  You should have received a copy of the GNU General Public License
  27  *  along with this program; if not, write to the Free Software
  28  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  29  *
  30  */
  31
  32 #include "squid.h"
  33
  34 /*
  35  *    Currently only byte ranges are supported
  36  *
  37  *    Essentially, there are three types of byte ranges:
  38  *
  39  *      1) first-byte-pos "-" last-byte-pos  // range
  40  *      2) first-byte-pos "-"                // trailer
  41  *      3)                "-" suffix-length  // suffix (last length bytes)
  42  *
  43  *
  44  *    When Range field is parsed, we have no clue about the content
  45  *    length of the document. Thus, we simply code an "absent" part
  46  *    using range_spec_unknown constant.
  47  *
  48  *    Note: when response length becomes known, we convert any range
  49  *    spec into type one above. (Canonization process).
  50  */
  51
  52
  53 /* local constants */
  54 #define range_spec_unknown ((size_t)-1)
  55
  56 /* local routines */
  57 #define known_spec(s) ((s) != range_spec_unknown)
  58 #define size_min(a,b) ((a) <= (b) ? (a) : (b))
  59 #define size_diff(a,b) ((a) >= (b) ? ((a)-(b)) : 0)
  60 static HttpHdrRangeSpec *httpHdrRangeSpecDup(const HttpHdrRangeSpec * spec);
  61 static int httpHdrRangeSpecCanonize(HttpHdrRangeSpec * spec, size_t clen);
  62 static void httpHdrRangeSpecPackInto(const HttpHdrRangeSpec * spec, Packer * p);
  63
  64 /* globals */
  65 static int RangeParsedCount = 0;
  66
  67 /*
  68  * Range-Spec
  69  */
  70
  71 static HttpHdrRangeSpec *
  72 httpHdrRangeSpecCreate()
  73 {
  74     return memAllocate(MEM_HTTP_HDR_RANGE_SPEC);
  75 }
  76
  77 /* parses range-spec and returns new object on success */
  78 static HttpHdrRangeSpec *
  79 httpHdrRangeSpecParseCreate(const char *field, int flen)
  80 {
  81     HttpHdrRangeSpec spec =
  82     {range_spec_unknown, range_spec_unknown};
  83     const char *p;
  84     if (flen < 2)
  85         return NULL;
  86     /* is it a suffix-byte-range-spec ? */
  87     if (*field == '-') {
  88         if (!httpHeaderParseSize(field + 1, &spec.length))
  89             return NULL;
  90     } else
  91         /* must have a '-' somewhere in _this_ field */
  92     if (!((p = strchr(field, '-')) || (p - field >= flen))) {
  93         debug(64, 2) ("ignoring invalid (missing '-') range-spec near: '%s'\n", field);
  94         return NULL;
  95     } else {
  96         if (!httpHeaderParseSize(field, &spec.offset))
  97             return NULL;
  98         p++;
  99         /* do we have last-pos ? */
 100         if (p - field < flen) {
 101             size_t last_pos;
 102             if (!httpHeaderParseSize(p, &last_pos))
 103                 return NULL;
 104             spec.length = size_diff(last_pos + 1, spec.offset);
 105         }
 106     }
 107     /* we managed to parse, check if the result makes sence */
 108     if (known_spec(spec.length) && !spec.length) {
 109         debug(64, 2) ("ignoring invalid (zero length) range-spec near: '%s'\n", field);
 110         return NULL;
 111     }
 112     return httpHdrRangeSpecDup(&spec);
 113 }
 114
 115 static void
 116 httpHdrRangeSpecDestroy(HttpHdrRangeSpec * spec)
 117 {
 118     memFree(MEM_HTTP_HDR_RANGE_SPEC, spec);
 119 }
 120
 121
 122 static HttpHdrRangeSpec *
 123 httpHdrRangeSpecDup(const HttpHdrRangeSpec * spec)
 124 {
 125     HttpHdrRangeSpec *dup = httpHdrRangeSpecCreate();
 126     dup->offset = spec->offset;
 127     dup->length = spec->length;
 128     return dup;
 129 }
 130
 131 static void
 132 httpHdrRangeSpecPackInto(const HttpHdrRangeSpec * spec, Packer * p)
 133 {
 134     if (!known_spec(spec->offset))      /* suffix */
 135         packerPrintf(p, "-%d", spec->length);
 136     else if (!known_spec(spec->length))         /* trailer */
 137         packerPrintf(p, "%d-", spec->offset);
 138     else                        /* range */
 139         packerPrintf(p, "%d-%d",
 140             spec->offset, spec->offset + spec->length - 1);
 141 }
 142
 143 /* fills "absent" positions in range specification based on response body size
 144  * returns true if the range is still valid
 145  * range is valid if its intersection with [0,length-1] is not empty
 146  */
 147 static int
 148 httpHdrRangeSpecCanonize(HttpHdrRangeSpec * spec, size_t clen)
 149 {
 150     debug(64, 5) ("httpHdrRangeSpecCanonize: have: [%d, %d) len: %d\n",
 151         spec->offset, spec->offset+spec->length, spec->length);
 152     if (!known_spec(spec->offset))      /* suffix */
 153         spec->offset = size_diff(clen, spec->length);
 154     else if (!known_spec(spec->length))         /* trailer */
 155         spec->length = size_diff(clen, spec->offset);
 156     /* we have a "range" now, adjust length if needed */
 157     assert(known_spec(spec->length));
 158     assert(known_spec(spec->offset));
 159     spec->length = size_min(size_diff(clen, spec->offset), spec->length);
 160     /* check range validity */
 161     debug(64, 5) ("httpHdrRangeSpecCanonize: done: [%d, %d) len: %d\n",
 162         spec->offset, spec->offset+spec->length, spec->length);
 163     return spec->length > 0;
 164 }
 165
 166 /* merges recepient with donor if possible; returns true on success
 167  * both specs must be canonized prior to merger, of course */
 168 static int
 169 httpHdrRangeSpecMergeWith(HttpHdrRangeSpec * recep, const HttpHdrRangeSpec * donor)
 170 {
 171     int merged = 0;
 172     size_t rhs = recep->offset + recep->length; /* no -1 ! */
 173     const size_t donor_rhs = donor->offset + donor->length; /* no -1 ! */
 174     assert(known_spec(recep->offset));
 175     assert(known_spec(donor->offset));
 176     assert(recep->length > 0);
 177     assert(donor->length > 0);
 178     /* do we have a left hand side overlap? */
 179     if (donor->offset < recep->offset && recep->offset <= donor_rhs) {
 180         recep->offset = donor->offset; /* decrease left offset */
 181         merged = 1;
 182     }
 183     /* do we have a right hand side overlap? */
 184     if (donor->offset <= rhs && rhs < donor_rhs) {
 185         rhs = donor_rhs; /* increase right offset */
 186         merged = 1;
 187     }
 188     /* adjust length if offsets have been changed */
 189     if (merged) {
 190         assert(rhs > recep->offset);
 191         recep->length = rhs - recep->offset;
 192     } else {
 193         /* does recepient contain donor? */
 194         merged =
 195             recep->offset <= donor->offset && donor->offset < rhs;
 196     }
 197     return merged;
 198 }
 199
 200 /*
 201  * Range
 202  */
 203
 204 HttpHdrRange *
 205 httpHdrRangeCreate()
 206 {
 207     HttpHdrRange *r = memAllocate(MEM_HTTP_HDR_RANGE);
 208     stackInit(&r->specs);
 209     return r;
 210 }
 211
 212 HttpHdrRange *
 213 httpHdrRangeParseCreate(const String * str)
 214 {
 215     HttpHdrRange *r = httpHdrRangeCreate();
 216     if (!httpHdrRangeParseInit(r, str)) {
 217         httpHdrRangeDestroy(r);
 218         r = NULL;
 219     }
 220     return r;
 221 }
 222
 223 /* returns true if ranges are valid; inits HttpHdrRange */
 224 int
 225 httpHdrRangeParseInit(HttpHdrRange * range, const String * str)
 226 {
 227     const char *item;
 228     const char *pos = NULL;
 229     int ilen;
 230     int count = 0;
 231     assert(range && str);
 232     RangeParsedCount++;
 233     debug(64, 8) ("parsing range field: '%s'\n", strBuf(*str));
 234     /* check range type */
 235     if (strNCaseCmp(*str, "bytes=", 6))
 236         return 0;
 237     /* skip "bytes="; hack! */
 238     pos = strBuf(*str) + 5;
 239     /* iterate through comma separated list */
 240     while (strListGetItem(str, ',', &item, &ilen, &pos)) {
 241         HttpHdrRangeSpec *spec = httpHdrRangeSpecParseCreate(item, ilen);
 242         /*
 243          * HTTP/1.1 draft says we must ignore the whole header field if one spec
 244          * is invalid. However, RFC 2068 just says that we must ignore that spec.
 245          */
 246         if (spec)
 247             stackPush(&range->specs, spec);
 248         count++;
 249     }
 250     debug(64, 8) ("parsed range range count: %d\n", range->specs.count);
 251     return range->specs.count;
 252 }
 253
 254 void
 255 httpHdrRangeDestroy(HttpHdrRange * range)
 256 {
 257     assert(range);
 258     while (range->specs.count)
 259         httpHdrRangeSpecDestroy(stackPop(&range->specs));
 260     stackClean(&range->specs);
 261     memFree(MEM_HTTP_HDR_RANGE, range);
 262 }
 263
 264 HttpHdrRange *
 265 httpHdrRangeDup(const HttpHdrRange * range)
 266 {
 267     HttpHdrRange *dup;
 268     int i;
 269     assert(range);
 270     dup = httpHdrRangeCreate();
 271     stackPrePush(&dup->specs, range->specs.count);
 272     for (i = 0; i < range->specs.count; i++)
 273         stackPush(&dup->specs, httpHdrRangeSpecDup(range->specs.items[i]));
 274     assert(range->specs.count == dup->specs.count);
 275     return dup;
 276 }
 277
 278 void
 279 httpHdrRangePackInto(const HttpHdrRange * range, Packer * p)
 280 {
 281     HttpHdrRangePos pos = HttpHdrRangeInitPos;
 282     const HttpHdrRangeSpec *spec;
 283     assert(range);
 284     while ((spec = httpHdrRangeGetSpec(range, &pos))) {
 285         if (pos != HttpHdrRangeInitPos)
 286             packerAppend(p, ",", 1);
 287         httpHdrRangeSpecPackInto(spec, p);
 288     }
 289 }
 290
 291 /*
 292  * canonizes all range specs within a set preserving the order
 293  * returns true if the set is valid after canonization;
 294  * the set is valid if
 295  *   - all range specs are valid and
 296  *   - there is at least one range spec
 297  */
 298 int
 299 httpHdrRangeCanonize(HttpHdrRange * range, size_t clen)
 300 {
 301     int i;
 302     HttpHdrRangeSpec *spec;
 303     HttpHdrRangePos pos = HttpHdrRangeInitPos;
 304     Stack goods;
 305     assert(range);
 306     assert(clen >= 0);
 307     stackInit(&goods);
 308     debug(64, 3) ("httpHdrRangeCanonize: started with %d specs, clen: %d\n", range->specs.count, clen);
 309
 310     /* canonize each entry and destroy bad ones if any */
 311     while ((spec = httpHdrRangeGetSpec(range, &pos))) {
 312         if (httpHdrRangeSpecCanonize(spec, clen))
 313             stackPush(&goods, spec);
 314         else
 315             httpHdrRangeSpecDestroy(spec);
 316     }
 317     debug(64, 3) ("httpHdrRangeCanonize: found %d bad specs\n",
 318         range->specs.count - goods.count);
 319     /* reset old array */
 320     stackClean(&range->specs);
 321     stackInit(&range->specs);
 322     /* merge specs:
 323      * take one spec for "goods" and merge specs from "range->specs"
 324      * with it until (no "range->specs" specs exist or no overlap) */
 325     for (i = 0; i < goods.count;) {
 326         HttpHdrRangeSpec *prev_spec = stackTop(&range->specs);
 327         spec = goods.items[i];
 328         if (prev_spec) {
 329             if (httpHdrRangeSpecMergeWith(spec, prev_spec)) {
 330                 /* merged with current so get rid of the prev one */
 331                 assert(prev_spec == stackPop(&range->specs));
 332                 httpHdrRangeSpecDestroy(prev_spec);
 333                 continue; /* re-iterate */
 334             }
 335         }
 336         stackPush(&range->specs, spec);
 337         i++; /* progress */
 338     }
 339     debug(64, 3) ("httpHdrRangeCanonize: merged %d specs\n",
 340         goods.count - range->specs.count);
 341     stackClean(&goods);
 342     debug(64, 3) ("httpHdrRangeCanonize: finished with %d specs\n",
 343         range->specs.count);
 344     return range->specs.count > 0;
 345 }
 346
 347 /* searches for next range, returns true if found */
 348 HttpHdrRangeSpec *
 349 httpHdrRangeGetSpec(const HttpHdrRange * range, HttpHdrRangePos *pos)
 350 {
 351     assert(range);
 352     assert(pos && *pos >= -1 && *pos < range->specs.count);
 353     (*pos)++;
 354     if (*pos < range->specs.count)
 355         return (HttpHdrRangeSpec *) range->specs.items[*pos];
 356     else
 357         return NULL;
 358 }
 359
 360 /* hack: returns true if range specs are too "complex" for Squid to handle */
 361 int
 362 httpHdrRangeIsComplex(const HttpHdrRange * range)
 363 {
 364     HttpHdrRangePos pos = HttpHdrRangeInitPos;
 365     const HttpHdrRangeSpec *spec;
 366     size_t offset = 0;
 367     assert(range);
 368     /* check that all rangers are in "strong" order */
 369     while ((spec = httpHdrRangeGetSpec(range, &pos))) {
 370         if (spec->offset < offset)
 371             return 1;
 372         offset = spec->offset + spec->length;
 373     }
 374     return 0;
 375 }
 376
 377 /* generates a "unique" boundary string for multipart responses
 378  * the caller is responsible for cleaning the string */
 379 String
 380 httpHdrRangeBoundaryStr(clientHttpRequest * http)
 381 {
 382     const char *key;
 383     String b = StringNull;
 384     assert(http);
 385     stringAppend(&b, full_appname_string, strlen(full_appname_string));
 386     stringAppend(&b, ":", 1);
 387     key = storeKeyText(http->entry->key);
 388     stringAppend(&b, key, strlen(key));
 389     return b;
 390 }