From 889b534a75a48a23e7f39694c30af9ba11365b78 Mon Sep 17 00:00:00 2001 From: rousskov <> Date: Fri, 5 Jun 1998 02:25:02 +0000 Subject: [PATCH] - canonization process for ranges will now merge overlapping ranges if any - cleanup --- ChangeLog | 6 +-- src/HttpHdrRange.cc | 115 ++++++++++++++++++++++++++++++++++---------- src/client_side.cc | 69 +++++++++++++++----------- src/protos.h | 2 +- src/structs.h | 2 +- 5 files changed, 134 insertions(+), 60 deletions(-) diff --git a/ChangeLog b/ChangeLog index ab8fb0f982..2b52bf7f0e 100644 --- a/ChangeLog +++ b/ChangeLog @@ -3,9 +3,9 @@ potentially cachable Range request for a not cached object, Squid requests the whole object from origin server and then replies with specified range(s) to the client. Multi-range requests are - supported. If-Range requests are supported. Limitations: - Multi-range requests with out of order or overlapping ranges are not - supported. + supported. Adjacent overlapping ranges are merged. If-Range requests + are supported. Limitations: Multi-range requests with out of order + ranges are not supported. - Made md5.c use standard memcpy and memset if they are avaliable. - Memory pools will now shrink if Squid is run-time reconfigured with smaller value of memory_pools_limit tag. diff --git a/src/HttpHdrRange.cc b/src/HttpHdrRange.cc index 2aca85bb98..69d95a3a2a 100644 --- a/src/HttpHdrRange.cc +++ b/src/HttpHdrRange.cc @@ -1,6 +1,6 @@ /* - * $Id: HttpHdrRange.cc,v 1.9 1998/06/02 21:38:04 rousskov Exp $ + * $Id: HttpHdrRange.cc,v 1.10 1998/06/04 20:25:03 rousskov Exp $ * * DEBUG: section 64 HTTP Range Header * AUTHOR: Alex Rousskov @@ -163,6 +163,40 @@ httpHdrRangeSpecCanonize(HttpHdrRangeSpec * spec, size_t clen) return spec->length > 0; } +/* merges recepient with donor if possible; returns true on success + * both specs must be canonized prior to merger, of course */ +static int +httpHdrRangeSpecMergeWith(HttpHdrRangeSpec * recep, const HttpHdrRangeSpec * donor) +{ + int merged = 0; + size_t rhs = recep->offset + recep->length; /* no -1 ! */ + const size_t donor_rhs = donor->offset + donor->length; /* no -1 ! */ + assert(known_spec(recep->offset)); + assert(known_spec(donor->offset)); + assert(recep->length > 0); + assert(donor->length > 0); + /* do we have a left hand side overlap? */ + if (donor->offset < recep->offset && recep->offset <= donor_rhs) { + recep->offset = donor->offset; /* decrease left offset */ + merged = 1; + } + /* do we have a right hand side overlap? */ + if (donor->offset <= rhs && rhs < donor_rhs) { + rhs = donor_rhs; /* increase right offset */ + merged = 1; + } + /* adjust length if offsets have been changed */ + if (merged) { + assert(rhs > recep->offset); + recep->length = rhs - recep->offset; + } else { + /* does recepient contain donor? */ + merged = + recep->offset <= donor->offset && donor->offset < rhs; + } + return merged; +} + /* * Range */ @@ -245,12 +279,12 @@ void httpHdrRangePackInto(const HttpHdrRange * range, Packer * p) { HttpHdrRangePos pos = HttpHdrRangeInitPos; - HttpHdrRangeSpec spec; + const HttpHdrRangeSpec *spec; assert(range); - while (httpHdrRangeGetSpec(range, &spec, &pos)) { + while ((spec = httpHdrRangeGetSpec(range, &pos))) { if (pos != HttpHdrRangeInitPos) packerAppend(p, ",", 1); - httpHdrRangeSpecPackInto(&spec, p); + httpHdrRangeSpecPackInto(spec, p); } } @@ -264,34 +298,63 @@ httpHdrRangePackInto(const HttpHdrRange * range, Packer * p) int httpHdrRangeCanonize(HttpHdrRange * range, size_t clen) { - int bad_count = 0; int i; + HttpHdrRangeSpec *spec; + HttpHdrRangePos pos = HttpHdrRangeInitPos; + Stack goods; assert(range); assert(clen >= 0); - for (i = 0; i < range->specs.count; i++) { - if (!httpHdrRangeSpecCanonize(range->specs.items[i], clen)) - bad_count++; + stackInit(&goods); + debug(64, 3) ("httpHdrRangeCanonize: started with %d specs, clen: %d\n", range->specs.count, clen); + + /* canonize each entry and destroy bad ones if any */ + while ((spec = httpHdrRangeGetSpec(range, &pos))) { + if (httpHdrRangeSpecCanonize(spec, clen)) + stackPush(&goods, spec); + else + httpHdrRangeSpecDestroy(spec); } - if (bad_count) - debug(64, 2) ("httpHdrRangeCanonize: found %d invalid specs out of %d\n", bad_count, range->specs.count); - else - debug(64, 3) ("httpHdrRangeCanonize: got %d valid specs\n", range->specs.count); - return !bad_count; + debug(64, 3) ("httpHdrRangeCanonize: found %d bad specs\n", + range->specs.count - goods.count); + /* reset old array */ + stackClean(&range->specs); + stackInit(&range->specs); + /* merge specs: + * take one spec for "goods" and merge specs from "range->specs" + * with it until (no "range->specs" specs exist or no overlap) */ + for (i = 0; i < goods.count;) { + HttpHdrRangeSpec *prev_spec = stackTop(&range->specs); + spec = goods.items[i]; + if (prev_spec) { + if (httpHdrRangeSpecMergeWith(spec, prev_spec)) { + /* merged with current so get rid of the prev one */ + assert(prev_spec == stackPop(&range->specs)); + httpHdrRangeSpecDestroy(prev_spec); + continue; /* re-iterate */ + } + } + stackPush(&range->specs, spec); + i++; /* progress */ + } + debug(64, 3) ("httpHdrRangeCanonize: merged %d specs\n", + goods.count - range->specs.count); + stackClean(&goods); + debug(64, 3) ("httpHdrRangeCanonize: finished with %d specs\n", + range->specs.count); + return range->specs.count > 0; } /* searches for next range, returns true if found */ -int -httpHdrRangeGetSpec(const HttpHdrRange * range, HttpHdrRangeSpec * spec, HttpHdrRangePos *pos) +HttpHdrRangeSpec * +httpHdrRangeGetSpec(const HttpHdrRange * range, HttpHdrRangePos *pos) { - assert(range && spec); + assert(range); assert(pos && *pos >= -1 && *pos < range->specs.count); (*pos)++; - if (*pos < range->specs.count) { - *spec = *(HttpHdrRangeSpec *) range->specs.items[*pos]; - return 1; - } - spec->offset = spec->length = 0; - return 0; + if (*pos < range->specs.count) + return (HttpHdrRangeSpec *) range->specs.items[*pos]; + else + return NULL; } /* hack: returns true if range specs are too "complex" for Squid to handle */ @@ -299,14 +362,14 @@ int httpHdrRangeIsComplex(const HttpHdrRange * range) { HttpHdrRangePos pos = HttpHdrRangeInitPos; - HttpHdrRangeSpec spec; + const HttpHdrRangeSpec *spec; size_t offset = 0; assert(range); /* check that all rangers are in "strong" order */ - while (httpHdrRangeGetSpec(range, &spec, &pos)) { - if (spec.offset < offset) + while ((spec = httpHdrRangeGetSpec(range, &pos))) { + if (spec->offset < offset) return 1; - offset = spec.offset + spec.length; + offset = spec->offset + spec->length; } return 0; } diff --git a/src/client_side.cc b/src/client_side.cc index fdfd282e79..f5cbbd6a55 100644 --- a/src/client_side.cc +++ b/src/client_side.cc @@ -1,6 +1,6 @@ /* - * $Id: client_side.cc,v 1.330 1998/06/04 18:57:08 wessels Exp $ + * $Id: client_side.cc,v 1.331 1998/06/04 20:25:04 rousskov Exp $ * * DEBUG: section 33 Client-side Routines * AUTHOR: Duane Wessels @@ -1130,15 +1130,15 @@ clientBuildRangeHeader(clientHttpRequest * http, HttpReply * rep) /* append appropriate header(s) */ if (spec_count == 1) { HttpHdrRangePos pos = HttpHdrRangeInitPos; - HttpHdrRangeSpec spec; - assert(httpHdrRangeGetSpec(http->request->range, &spec, &pos)); + const HttpHdrRangeSpec *spec = httpHdrRangeGetSpec(http->request->range, &pos); + assert(spec); /* append Content-Range */ - httpHeaderAddContRange(hdr, spec, rep->content_length); + httpHeaderAddContRange(hdr, *spec, rep->content_length); /* set new Content-Length to the actual number of OCTETs * transmitted in the message-body */ httpHeaderDelById(hdr, HDR_CONTENT_LENGTH); - httpHeaderPutInt(hdr, HDR_CONTENT_LENGTH, spec.length); - debug(33, 2) ("clientBuildRangeHeader: actual content length: %d\n", spec.length); + httpHeaderPutInt(hdr, HDR_CONTENT_LENGTH, spec->length); + debug(33, 2) ("clientBuildRangeHeader: actual content length: %d\n", spec->length); } else { /* multipart! */ /* generate boundary string */ @@ -1282,11 +1282,12 @@ clientPackRange(clientHttpRequest *http, HttpHdrRangeIter *i, const char **buf, const size_t copy_sz = i->debt_size <= *size ? i->debt_size : *size; off_t body_off = http->out.offset - i->prefix_size; assert(*size > 0); + assert(i->spec); /* intersection of "have" and "need" ranges must not be empty */ - assert(body_off < i->spec.offset + i->spec.length); - assert(body_off + *size > i->spec.offset); + assert(body_off < i->spec->offset + i->spec->length); + assert(body_off + *size > i->spec->offset); /* put boundary and headers at the beginning of range in a multi-range */ - if (http->request->range->specs.count > 1 && i->debt_size == i->spec.length) { + if (http->request->range->specs.count > 1 && i->debt_size == i->spec->length) { HttpReply *rep = http->entry->mem_obj ? /* original reply */ http->entry->mem_obj->reply : NULL; HttpHeader hdr; @@ -1299,7 +1300,7 @@ clientPackRange(clientHttpRequest *http, HttpHdrRangeIter *i, const char **buf, httpHeaderInit(&hdr, hoReply); if (httpHeaderHas(&rep->header, HDR_CONTENT_TYPE)) httpHeaderPutStr(&hdr, HDR_CONTENT_TYPE, httpHeaderGetStr(&rep->header, HDR_CONTENT_TYPE)); - httpHeaderAddContRange(&hdr, i->spec, rep->content_length); + httpHeaderAddContRange(&hdr, *i->spec, rep->content_length); packerToMemInit(&p, mb); httpHeaderPackInto(&hdr, &p); packerClean(&p); @@ -1320,6 +1321,21 @@ clientPackRange(clientHttpRequest *http, HttpHdrRangeIter *i, const char **buf, assert(*size >= 0 && i->debt_size >= 0); } +/* returns true if there is still data available to pack more ranges + * increments iterator "i" + * used by clientPackMoreRanges */ +static int +clientCanPackMoreRanges(const clientHttpRequest *http, HttpHdrRangeIter *i, ssize_t size) +{ + /* first update "i" if needed */ + if (!i->debt_size) { + if ((i->spec = httpHdrRangeGetSpec(http->request->range, &i->pos))) + i->debt_size = i->spec->length; + } + assert(!i->debt_size == !i->spec); /* paranoid sync condition */ + /* continue condition: need_more_data && have_more_data */ + return i->spec && size > 0; +} /* extracts "ranges" from buf and appends them to mb, updating all offsets and such */ /* returns true if we need more data */ @@ -1327,24 +1343,19 @@ static int clientPackMoreRanges(clientHttpRequest *http, const char *buf, ssize_t size, MemBuf *mb) { HttpHdrRangeIter *i = &http->range_iter; - int need_more = i->debt_size > 0; /* offset in range specs does not count the prefix of an http msg */ off_t body_off = http->out.offset - i->prefix_size; assert(size >= 0); /* filter out data according to range specs */ /* note: order of loop conditions is significant! */ - while ((i->debt_size || (need_more = httpHdrRangeGetSpec(http->request->range, &i->spec, &i->pos))) && - size > 0) { + while (clientCanPackMoreRanges(http, i, size)) { off_t start; /* offset of still missing data */ - if (!i->debt_size) - i->debt_size = i->spec.length; - if (!i->debt_size) - continue; - start = i->spec.offset + i->spec.length - i->debt_size; + assert(i->spec); + start = i->spec->offset + i->spec->length - i->debt_size; debug(33, 2) ("clientPackMoreRanges: in: offset: %d size: %d\n", (int)body_off, size); debug(33, 2) ("clientPackMoreRanges: out: start: %d spec[%d]: [%d, %d), len: %d debt: %d\n", - (int)start, (int)i->pos, i->spec.offset, (int)(i->spec.offset+i->spec.length), i->spec.length, i->debt_size); + (int)start, (int)i->pos, i->spec->offset, (int)(i->spec->offset+i->spec->length), i->spec->length, i->debt_size); assert(body_off <= start); /* we did not miss it */ /* skip up to start */ if (body_off + size > start) { @@ -1365,17 +1376,17 @@ clientPackMoreRanges(clientHttpRequest *http, const char *buf, ssize_t size, Mem body_off = http->out.offset - i->prefix_size; /* sync */ } } + assert(!i->debt_size == !i->spec); /* paranoid sync condition */ debug(33, 2) ("clientPackMoreRanges: buf exhausted: in: offset: %d size: %d need_more: %d\n", - (int)body_off, size, need_more); - debug(33, 2) ("clientPackMoreRanges: spec[%d]: [%d, %d), len: %d debt: %d\n", - (int)i->pos, i->spec.offset, (int)(i->spec.offset+i->spec.length), i->spec.length, i->debt_size); - /* skip the data we do not need */ - /* maybe, we have not seen that data yet! */ - if (need_more) { - if (i->debt_size == i->spec.length) /* at the start of the cur. spec */ - body_off = i->spec.offset; + (int)body_off, size, i->debt_size); + if (i->debt_size) { + debug(33, 2) ("clientPackMoreRanges: need more: spec[%d]: [%d, %d), len: %d\n", + (int)i->pos, i->spec->offset, (int)(i->spec->offset+i->spec->length), i->spec->length); + /* skip the data we do not need if possible */ + if (i->debt_size == i->spec->length) /* at the start of the cur. spec */ + body_off = i->spec->offset; else - assert(body_off == i->spec.offset + i->spec.length - i->debt_size); + assert(body_off == i->spec->offset + i->spec->length - i->debt_size); } else if (http->request->range->specs.count > 1) { /* put terminating boundary for multiparts */ @@ -1383,7 +1394,7 @@ clientPackMoreRanges(clientHttpRequest *http, const char *buf, ssize_t size, Mem } http->out.offset = body_off + i->prefix_size; /* sync */ - return need_more; + return i->debt_size > 0; } /* diff --git a/src/protos.h b/src/protos.h index 37b8be9e57..a31effd374 100644 --- a/src/protos.h +++ b/src/protos.h @@ -293,7 +293,7 @@ extern void httpHdrRangeDestroy(HttpHdrRange * range); extern HttpHdrRange *httpHdrRangeDup(const HttpHdrRange * range); extern void httpHdrRangePackInto(const HttpHdrRange * range, Packer * p); /* iterate through specs */ -extern int httpHdrRangeGetSpec(const HttpHdrRange * range, HttpHdrRangeSpec * spec, HttpHdrRangePos * pos); +extern HttpHdrRangeSpec *httpHdrRangeGetSpec(const HttpHdrRange * range, HttpHdrRangePos * pos); /* adjust specs after the length is known */ extern int httpHdrRangeCanonize(HttpHdrRange * range, size_t clen); /* other */ diff --git a/src/structs.h b/src/structs.h index f5aa4158f6..522fd0e3e7 100644 --- a/src/structs.h +++ b/src/structs.h @@ -541,8 +541,8 @@ struct _TimeOrTag { /* data for iterating thru range specs */ struct _HttpHdrRangeIter { - HttpHdrRangeSpec spec; HttpHdrRangePos pos; + const HttpHdrRangeSpec *spec; /* current spec at pos */ size_t debt_size; /* bytes left to send from the current spec */ size_t prefix_size; /* the size of the incoming HTTP msg prefix */ String boundary; /* boundary for multipart responses */ -- 2.47.3