# HG changeset patch
# User hucongcong <hucong.c@foxmail.com>
# Date 1509099940 -28800
# Fri Oct 27 18:25:40 2017 +0800
# Node ID 62c100a0d42614cd46f0719c0acb0ad914594217
# Parent b9850d3deb277bd433a689712c40a84401443520
Range filter: support multiple ranges.

When multiple ranges are requested, nginx will coalesce any of the ranges
that overlap, or that are separated by a gap that is smaller than the
NGX_HTTP_RANGE_MULTIPART_GAP macro.

diff -r b9850d3deb27 -r 62c100a0d426 src/http/modules/ngx_http_range_filter_module.c
--- a/src/http/modules/ngx_http_range_filter_module.c Fri Oct 27 18:21:00 2017 +0800
+++ b/src/http/modules/ngx_http_range_filter_module.c Fri Oct 27 18:25:40 2017 +0800
@@ -45,33 +45,34 @@
*/


-typedef struct {
- off_t start;
- off_t end;
- ngx_str_t content_range;
-} ngx_http_range_t;
+#define NGX_HTTP_RANGE_MULTIPART_GAP 80


typedef struct {
- off_t offset;
- ngx_str_t boundary_header;
- ngx_array_t ranges;
+ off_t offset;
+ ngx_uint_t index; /* start with 1 */
+
+ ngx_str_t boundary_header;
} ngx_http_range_filter_ctx_t;


static ngx_int_t ngx_http_range_parse(ngx_http_request_t *r,
ngx_http_range_filter_ctx_t *ctx, ngx_uint_t ranges);
+static int ngx_libc_cdecl ngx_http_range_cmp(const void *one, const void *two);
+static void ngx_http_range_coalesce(ngx_http_request_t *r);
static ngx_int_t ngx_http_range_singlepart_header(ngx_http_request_t *r,
ngx_http_range_filter_ctx_t *ctx);
static ngx_int_t ngx_http_range_multipart_header(ngx_http_request_t *r,
ngx_http_range_filter_ctx_t *ctx);
static ngx_int_t ngx_http_range_not_satisfiable(ngx_http_request_t *r);
-static ngx_int_t ngx_http_range_test_overlapped(ngx_http_request_t *r,
- ngx_http_range_filter_ctx_t *ctx, ngx_chain_t *in);
static ngx_int_t ngx_http_range_singlepart_body(ngx_http_request_t *r,
ngx_http_range_filter_ctx_t *ctx, ngx_chain_t *in);
static ngx_int_t ngx_http_range_multipart_body(ngx_http_request_t *r,
ngx_http_range_filter_ctx_t *ctx, ngx_chain_t *in);
+static ngx_int_t ngx_http_range_link_boundary_header(ngx_http_request_t *r,
+ ngx_http_range_filter_ctx_t *ctx, ngx_chain_t ***lll);
+static ngx_int_t ngx_http_range_link_last_boundary(ngx_http_request_t *r,
+ ngx_http_range_filter_ctx_t *ctx, ngx_chain_t **ll);

static ngx_int_t ngx_http_range_header_filter_init(ngx_conf_t *cf);
static ngx_int_t ngx_http_range_body_filter_init(ngx_conf_t *cf);
@@ -234,7 +235,7 @@ parse:
r->headers_out.status = NGX_HTTP_PARTIAL_CONTENT;
r->headers_out.status_line.len = 0;

- if (ctx->ranges.nelts == 1) {
+ if (r->headers_out.ranges->nelts == 1) {
return ngx_http_range_singlepart_header(r, ctx);
}

@@ -270,9 +271,9 @@ ngx_http_range_parse(ngx_http_request_t
ngx_uint_t ranges)
{
u_char *p;
- off_t start, end, size, content_length, cutoff,
- cutlim;
- ngx_uint_t suffix;
+ off_t start, end, content_length,
+ cutoff, cutlim;
+ ngx_uint_t suffix, unordered;
ngx_http_range_t *range;
ngx_http_range_filter_ctx_t *mctx;

@@ -280,19 +281,21 @@ ngx_http_range_parse(ngx_http_request_t
mctx = ngx_http_get_module_ctx(r->main,
ngx_http_range_body_filter_module);
if (mctx) {
- ctx->ranges = mctx->ranges;
+ r->headers_out.ranges = r->main->headers_out.ranges;
+ ctx->boundary_header = mctx->boundary_header;
return NGX_OK;
}
}

- if (ngx_array_init(&ctx->ranges, r->pool, 1, sizeof(ngx_http_range_t))
- != NGX_OK)
- {
+ r->headers_out.ranges = ngx_array_create(r->pool, 1,
+ sizeof(ngx_http_range_t));
+ if (r->headers_out.ranges == NULL) {
return NGX_ERROR;
}

p = r->headers_in.range->value.data + 6;
- size = 0;
+ range = NULL;
+ unordered = 0;
content_length = r->headers_out.content_length_n;

cutoff = NGX_MAX_OFF_T_VALUE / 10;
@@ -374,7 +377,22 @@ ngx_http_range_parse(ngx_http_request_t
return NGX_DECLINED;
}

- range = ngx_array_push(&ctx->ranges);
+ if (range) {
+
+ if (start < range->start) {
+ unordered++;
+
+ } else if (start - NGX_HTTP_RANGE_MULTIPART_GAP < range->end) {
+ r->headers_out.ranges->nelts--;
+ start = range->start;
+
+ if (range->end > end) {
+ end = range->end;
+ }
+ }
+ }
+
+ range = ngx_array_push(r->headers_out.ranges);
if (range == NULL) {
return NGX_ERROR;
}
@@ -382,12 +400,6 @@ ngx_http_range_parse(ngx_http_request_t
range->start = start;
range->end = end;

- if (size > NGX_MAX_OFF_T_VALUE - (end - start)) {
- return NGX_HTTP_RANGE_NOT_SATISFIABLE;
- }
-
- size += end - start;
-
} else if (start == 0) {
return NGX_DECLINED;
}
@@ -397,15 +409,73 @@ ngx_http_range_parse(ngx_http_request_t
}
}

- if (ctx->ranges.nelts == 0) {
+ if (unordered) {
+ ngx_qsort(r->headers_out.ranges->elts, r->headers_out.ranges->nelts,
+ sizeof(ngx_http_range_t), ngx_http_range_cmp);
+
+ ngx_http_range_coalesce(r);
+ }
+
+ if (r->headers_out.ranges->nelts == 0) {
return NGX_HTTP_RANGE_NOT_SATISFIABLE;
}

- if (size > content_length) {
- return NGX_DECLINED;
+ return NGX_OK;
+}
+
+
+static int ngx_libc_cdecl
+ngx_http_range_cmp(const void *one, const void *two)
+{
+ ngx_http_range_t *first = (ngx_http_range_t *) one;
+ ngx_http_range_t *second = (ngx_http_range_t *) two;
+
+ if (first->start > second->start) {
+ return 1;
+ }
+
+ if (first->start < second->start) {
+ return -1;
+ }
+
+ if (first->end < second->end) {
+ return 1;
+ }
+
+ if (first->end > second->end) {
+ return -1;
}

- return NGX_OK;
+ return 0;
+}
+
+
+static void
+ngx_http_range_coalesce(ngx_http_request_t *r)
+{
+ ngx_uint_t i, j;
+ ngx_http_range_t *range;
+
+ range = r->headers_out.ranges->elts;
+ for (i = 0, j = 1; j < r->headers_out.ranges->nelts; j++) {
+
+ if (range[j].end <= range[i].end) {
+ continue;
+ }
+
+ if (range[j].start - NGX_HTTP_RANGE_MULTIPART_GAP < range[i].end) {
+ range[i].end = range[j].end;
+ continue;
+ }
+
+ i++;
+ if (i != j) {
+ range[i].start = range[j].start;
+ range[i].end = range[j].end;
+ }
+ }
+
+ r->headers_out.ranges->nelts = i + 1;
}


@@ -440,7 +510,7 @@ ngx_http_range_singlepart_header(ngx_htt

/* "Content-Range: bytes SSSS-EEEE/TTTT" header */

- range = ctx->ranges.elts;
+ range = r->headers_out.ranges->elts;

content_range->value.len = ngx_sprintf(content_range->value.data,
"bytes %O-%O/%O",
@@ -470,6 +540,10 @@ ngx_http_range_multipart_header(ngx_http
ngx_http_range_t *range;
ngx_atomic_uint_t boundary;

+ if (r != r->main) {
+ return ngx_http_next_header_filter(r);
+ }
+
size = sizeof(CRLF "--") - 1 + NGX_ATOMIC_T_LEN
+ sizeof(CRLF "Content-Type: ") - 1
+ r->headers_out.content_type.len
@@ -552,8 +626,8 @@ ngx_http_range_multipart_header(ngx_http

len = sizeof(CRLF "--") - 1 + NGX_ATOMIC_T_LEN + sizeof("--" CRLF) - 1;

- range = ctx->ranges.elts;
- for (i = 0; i < ctx->ranges.nelts; i++) {
+ range = r->headers_out.ranges->elts;
+ for (i = 0; i < r->headers_out.ranges->nelts; i++) {

/* the size of the range: "SSSS-EEEE/TTTT" CRLF CRLF */

@@ -571,10 +645,11 @@ ngx_http_range_multipart_header(ngx_http
- range[i].content_range.data;

len += ctx->boundary_header.len + range[i].content_range.len
- + (range[i].end - range[i].start);
+ + (range[i].end - range[i].start);
}

r->headers_out.content_length_n = len;
+ r->headers_out.content_offset = range[0].start;

if (r->headers_out.content_length) {
r->headers_out.content_length->hash = 0;
@@ -636,67 +711,19 @@ ngx_http_range_body_filter(ngx_http_requ
return ngx_http_next_body_filter(r, in);
}

- if (ctx->ranges.nelts == 1) {
+ if (r->headers_out.ranges->nelts == 1) {
return ngx_http_range_singlepart_body(r, ctx, in);
}

- /*
- * multipart ranges are supported only if whole body is in a single buffer
- */
-
if (ngx_buf_special(in->buf)) {
return ngx_http_next_body_filter(r, in);
}

- if (ngx_http_range_test_overlapped(r, ctx, in) != NGX_OK) {
- return NGX_ERROR;
- }
-
return ngx_http_range_multipart_body(r, ctx, in);
}


static ngx_int_t
-ngx_http_range_test_overlapped(ngx_http_request_t *r,
- ngx_http_range_filter_ctx_t *ctx, ngx_chain_t *in)
-{
- off_t start, last;
- ngx_buf_t *buf;
- ngx_uint_t i;
- ngx_http_range_t *range;
-
- if (ctx->offset) {
- goto overlapped;
- }
-
- buf = in->buf;
-
- if (!buf->last_buf) {
- start = ctx->offset;
- last = ctx->offset + ngx_buf_size(buf);
-
- range = ctx->ranges.elts;
- for (i = 0; i < ctx->ranges.nelts; i++) {
- if (start > range[i].start || last < range[i].end) {
- goto overlapped;
- }
- }
- }
-
- ctx->offset = ngx_buf_size(buf);
-
- return NGX_OK;
-
-overlapped:
-
- ngx_log_error(NGX_LOG_ALERT, r->connection->log, 0,
- "range in overlapped buffers");
-
- return NGX_ERROR;
-}
-
-
-static ngx_int_t
ngx_http_range_singlepart_body(ngx_http_request_t *r,
ngx_http_range_filter_ctx_t *ctx, ngx_chain_t *in)
{
@@ -707,7 +734,7 @@ ngx_http_range_singlepart_body(ngx_http_

out = NULL;
ll = &out;
- range = ctx->ranges.elts;
+ range = r->headers_out.ranges->elts;

for (cl = in; cl; cl = cl->next) {

@@ -787,96 +814,227 @@ static ngx_int_t
ngx_http_range_multipart_body(ngx_http_request_t *r,
ngx_http_range_filter_ctx_t *ctx, ngx_chain_t *in)
{
- ngx_buf_t *b, *buf;
- ngx_uint_t i;
- ngx_chain_t *out, *hcl, *rcl, *dcl, **ll;
- ngx_http_range_t *range;
+ off_t start, last, back;
+ ngx_buf_t *buf, *b;
+ ngx_uint_t i, finished;
+ ngx_chain_t *out, *cl, *ncl, **ll;
+ ngx_http_range_t *range, *tail;
+
+ range = r->headers_out.ranges->elts;

- ll = &out;
- buf = in->buf;
- range = ctx->ranges.elts;
+ if (!ctx->index) {
+ for (i = 0; i < r->headers_out.ranges->nelts; i++) {
+ if (ctx->offset < range[i].end) {
+ ctx->index = i + 1;
+ break;
+ }
+ }
+ }

- for (i = 0; i < ctx->ranges.nelts; i++) {
+ tail = range + r->headers_out.ranges->nelts - 1;
+ range += ctx->index - 1;

- /*
- * The boundary header of the range:
- * CRLF
- * "--0123456789" CRLF
- * "Content-Type: image/jpeg" CRLF
- * "Content-Range: bytes "
- */
+ out = NULL;
+ ll = &out;
+ finished = 0;
+
+ for (cl = in; cl; cl = cl->next) {
+
+ buf = cl->buf;

- b = ngx_calloc_buf(r->pool);
- if (b == NULL) {
- return NGX_ERROR;
+ start = ctx->offset;
+ last = ctx->offset + ngx_buf_size(buf);
+
+ ctx->offset = last;
+
+ ngx_log_debug2(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
+ "http range multipart body buf: %O-%O", start, last);
+
+ if (ngx_buf_special(buf)) {
+ *ll = cl;
+ ll = &cl->next;
+ continue;
}

- b->memory = 1;
- b->pos = ctx->boundary_header.data;
- b->last = ctx->boundary_header.data + ctx->boundary_header.len;
+ if (range->end <= start || range->start >= last) {
+
+ ngx_log_debug0(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
+ "http range multipart body skip");

- hcl = ngx_alloc_chain_link(r->pool);
- if (hcl == NULL) {
- return NGX_ERROR;
+ if (buf->in_file) {
+ buf->file_pos = buf->file_last;
+ }
+
+ buf->pos = buf->last;
+ buf->sync = 1;
+
+ continue;
}

- hcl->buf = b;
+ if (range->start >= start) {

+ if (ngx_http_range_link_boundary_header(r, ctx, &ll) != NGX_OK) {
+ return NGX_ERROR;
+ }

- /* "SSSS-EEEE/TTTT" CRLF CRLF */
+ if (buf->in_file) {
+ buf->file_pos += range->start - start;
+ }

- b = ngx_calloc_buf(r->pool);
- if (b == NULL) {
- return NGX_ERROR;
+ if (ngx_buf_in_memory(buf)) {
+ buf->pos += (size_t) (range->start - start);
+ }
}

- b->temporary = 1;
- b->pos = range[i].content_range.data;
- b->last = range[i].content_range.data + range[i].content_range.len;
+ if (range->end <= last) {
+
+ if (range < tail && range[1].start < last) {
+
+ b = ngx_alloc_buf(r->pool);
+ if (b == NULL) {
+ return NGX_ERROR;
+ }
+
+ ncl = ngx_alloc_chain_link(r->pool);
+ if (ncl == NULL) {
+ return NGX_ERROR;
+ }

- rcl = ngx_alloc_chain_link(r->pool);
- if (rcl == NULL) {
- return NGX_ERROR;
- }
+ ncl->buf = b;
+ ncl->next = cl;
+
+ ngx_memcpy(b, buf, sizeof(ngx_buf_t));
+ b->last_in_chain = 0;
+ b->last_buf = 0;
+
+ back = last - range->end;
+ ctx->offset -= back;
+
+ ngx_log_debug2(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
+ "http range multipart body reuse buf: %O-%O",
+ ctx->offset, ctx->offset + back);

- rcl->buf = b;
+ if (buf->in_file) {
+ buf->file_pos = buf->file_last - back;
+ }
+
+ if (ngx_buf_in_memory(buf)) {
+ buf->pos = buf->last - back;
+ }

+ cl = ncl;
+ buf = cl->buf;
+ }
+
+ if (buf->in_file) {
+ buf->file_last -= last - range->end;
+ }

- /* the range data */
+ if (ngx_buf_in_memory(buf)) {
+ buf->last -= (size_t) (last - range->end);
+ }

- b = ngx_calloc_buf(r->pool);
- if (b == NULL) {
- return NGX_ERROR;
+ if (range == tail) {
+ buf->last_buf = (r == r->main) ? 1 : 0;
+ buf->last_in_chain = 1;
+ *ll = cl;
+ ll = &cl->next;
+
+ finished = 1;
+ break;
+ }
+
+ range++;
+ ctx->index++;
}

- b->in_file = buf->in_file;
- b->temporary = buf->temporary;
- b->memory = buf->memory;
- b->mmap = buf->mmap;
- b->file = buf->file;
+ *ll = cl;
+ ll = &cl->next;
+ }
+
+ if (out == NULL) {
+ return NGX_OK;
+ }
+
+ *ll = NULL;
+
+ if (finished
+ && ngx_http_range_link_last_boundary(r, ctx, ll) != NGX_OK)
+ {
+ return NGX_ERROR;
+ }
+
+ return ngx_http_next_body_filter(r, out);
+}
+

- if (buf->in_file) {
- b->file_pos = buf->file_pos + range[i].start;
- b->file_last = buf->file_pos + range[i].end;
- }
+static ngx_int_t
+ngx_http_range_link_boundary_header(ngx_http_request_t *r,
+ ngx_http_range_filter_ctx_t *ctx, ngx_chain_t ***lll)
+{
+ ngx_buf_t *b;
+ ngx_chain_t *hcl, *rcl;
+ ngx_http_range_t *range;
+
+ /*
+ * The boundary header of the range:
+ * CRLF
+ * "--0123456789" CRLF
+ * "Content-Type: image/jpeg" CRLF
+ * "Content-Range: bytes "
+ */
+
+ b = ngx_calloc_buf(r->pool);
+ if (b == NULL) {
+ return NGX_ERROR;
+ }

- if (ngx_buf_in_memory(buf)) {
- b->pos = buf->pos + (size_t) range[i].start;
- b->last = buf->pos + (size_t) range[i].end;
- }
+ b->memory = 1;
+ b->pos = ctx->boundary_header.data;
+ b->last = ctx->boundary_header.data + ctx->boundary_header.len;
+
+ hcl = ngx_alloc_chain_link(r->pool);
+ if (hcl == NULL) {
+ return NGX_ERROR;
+ }
+
+ hcl->buf = b;
+
+
+ /* "SSSS-EEEE/TTTT" CRLF CRLF */
+
+ b = ngx_calloc_buf(r->pool);
+ if (b == NULL) {
+ return NGX_ERROR;
+ }

- dcl = ngx_alloc_chain_link(r->pool);
- if (dcl == NULL) {
- return NGX_ERROR;
- }
+ range = r->headers_out.ranges->elts;
+ b->temporary = 1;
+ b->pos = range[ctx->index - 1].content_range.data;
+ b->last = range[ctx->index - 1].content_range.data
+ + range[ctx->index - 1].content_range.len;
+
+ rcl = ngx_alloc_chain_link(r->pool);
+ if (rcl == NULL) {
+ return NGX_ERROR;
+ }
+
+ rcl->buf = b;

- dcl->buf = b;
+ **lll = hcl;
+ hcl->next = rcl;
+ *lll = &rcl->next;
+
+ return NGX_OK;
+}

- *ll = hcl;
- hcl->next = rcl;
- rcl->next = dcl;
- ll = &dcl->next;
- }
+
+static ngx_int_t
+ngx_http_range_link_last_boundary(ngx_http_request_t *r,
+ ngx_http_range_filter_ctx_t *ctx, ngx_chain_t **ll)
+{
+ ngx_buf_t *b;
+ ngx_chain_t *hcl;

/* the last boundary CRLF "--0123456789--" CRLF */

@@ -886,7 +1044,8 @@ ngx_http_range_multipart_body(ngx_http_r
}

b->temporary = 1;
- b->last_buf = 1;
+ b->last_in_chain = 1;
+ b->last_buf = (r == r->main) ? 1 : 0;

b->pos = ngx_pnalloc(r->pool, sizeof(CRLF "--") - 1 + NGX_ATOMIC_T_LEN
+ sizeof("--" CRLF) - 1);
@@ -909,7 +1068,7 @@ ngx_http_range_multipart_body(ngx_http_r

*ll = hcl;

- return ngx_http_next_body_filter(r, out);
+ return NGX_OK;
}


diff -r b9850d3deb27 -r 62c100a0d426 src/http/ngx_http_request.h
--- a/src/http/ngx_http_request.h Fri Oct 27 18:21:00 2017 +0800
+++ b/src/http/ngx_http_request.h Fri Oct 27 18:25:40 2017 +0800
@@ -251,6 +251,13 @@ typedef struct {


typedef struct {
+ off_t start;
+ off_t end;
+ ngx_str_t content_range;
+} ngx_http_range_t;
+
+
+typedef struct {
ngx_list_t headers;
ngx_list_t trailers;

@@ -278,6 +285,7 @@ typedef struct {
u_char *content_type_lowcase;
ngx_uint_t content_type_hash;

+ ngx_array_t *ranges; /* ngx_http_range_t */
ngx_array_t cache_control;

off_t content_length_n;
_______________________________________________
nginx-devel mailing list
nginx-devel@nginx.org
http://mailman.nginx.org/mailman/listinfo/nginx-devel