[patch-1] Range filter: support multiple ranges.

胡聪 (hucc) hucong.c at foxmail.com
Fri Oct 27 10:50:32 UTC 2017


# HG changeset patch
# User hucongcong <hucong.c at 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;


More information about the nginx-devel mailing list