You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@apr.apache.org by mi...@apache.org on 2021/10/19 14:30:38 UTC
svn commit: r1894380 - in /apr/apr/trunk: buckets/apr_brigade.c
include/apr_buckets.h test/testbuckets.c
Author: minfrin
Date: Tue Oct 19 14:30:37 2021
New Revision: 1894380
URL: http://svn.apache.org/viewvc?rev=1894380&view=rev
Log:
apr_brigades: Add apr_brigade_split_boundary(), allowing us to split
brigades on boundaries of arbitrary length.
Modified:
apr/apr/trunk/buckets/apr_brigade.c
apr/apr/trunk/include/apr_buckets.h
apr/apr/trunk/test/testbuckets.c
Modified: apr/apr/trunk/buckets/apr_brigade.c
URL: http://svn.apache.org/viewvc/apr/apr/trunk/buckets/apr_brigade.c?rev=1894380&r1=1894379&r2=1894380&view=diff
==============================================================================
--- apr/apr/trunk/buckets/apr_brigade.c (original)
+++ apr/apr/trunk/buckets/apr_brigade.c Tue Oct 19 14:30:37 2021
@@ -387,6 +387,269 @@ APR_DECLARE(apr_status_t) apr_brigade_sp
return APR_SUCCESS;
}
+APR_DECLARE(apr_status_t) apr_brigade_split_boundary(apr_bucket_brigade *bbOut,
+ apr_bucket_brigade *bbIn,
+ apr_read_type_e block,
+ const char *boundary,
+ apr_size_t boundary_len,
+ apr_off_t maxbytes)
+{
+ apr_off_t outbytes = 0;
+
+ if (!boundary || !boundary[0]) {
+ return APR_EINVAL;
+ }
+
+ if (APR_BUCKETS_STRING == boundary_len) {
+ boundary_len = strlen(boundary);
+ }
+
+ /*
+ * While the call describes itself as searching for a boundary string,
+ * what we actually do is search for anything that is definitely not
+ * a boundary string, and allow that not-boundary data to pass through.
+ *
+ * If we find data that might be a boundary, we try read more data in
+ * until we know for sure.
+ */
+ while (!APR_BRIGADE_EMPTY(bbIn)) {
+
+ const char *pos;
+ const char *str;
+ apr_bucket *e, *next, *prev;
+ apr_off_t inbytes = 0;
+ apr_size_t len;
+ apr_status_t rv;
+
+ /* We didn't find a boundary within the maximum line length. */
+ if (outbytes >= maxbytes) {
+ return APR_INCOMPLETE;
+ }
+
+ e = APR_BRIGADE_FIRST(bbIn);
+
+ /* We hit a metadata bucket, stop and let the caller handle it */
+ if (APR_BUCKET_IS_METADATA(e)) {
+ return APR_INCOMPLETE;
+ }
+
+ rv = apr_bucket_read(e, &str, &len, block);
+
+ if (rv != APR_SUCCESS) {
+ return rv;
+ }
+
+ inbytes += len;
+
+ /*
+ * Fast path.
+ *
+ * If we have at least one boundary worth of data, do an optimised
+ * substring search for the boundary, and split quickly if found.
+ */
+ if (len >= boundary_len) {
+
+ apr_size_t off;
+ apr_size_t leftover;
+
+ pos = strnstr(str, boundary, len);
+
+ /* definitely found it, we leave */
+ if (pos != NULL) {
+
+ off = pos - str;
+
+ /* everything up to the boundary */
+ if (off) {
+
+ apr_bucket_split(e, off);
+ APR_BUCKET_REMOVE(e);
+ APR_BRIGADE_INSERT_TAIL(bbOut, e);
+
+ e = APR_BRIGADE_FIRST(bbIn);
+ }
+
+ /* cut out the boundary */
+ apr_bucket_split(e, boundary_len);
+ apr_bucket_delete(e);
+
+ return APR_SUCCESS;
+ }
+
+ /* any partial matches at the end? */
+ leftover = boundary_len - 1;
+ off = (len - leftover);
+
+ while (leftover) {
+ if (!strncmp(str + off, boundary, leftover)) {
+
+ if (off) {
+
+ apr_bucket_split(e, off);
+ APR_BUCKET_REMOVE(e);
+ APR_BRIGADE_INSERT_TAIL(bbOut, e);
+
+ e = APR_BRIGADE_FIRST(bbIn);
+ }
+
+ outbytes += off;
+ inbytes -= off;
+
+ goto skip;
+ }
+ off++;
+ leftover--;
+ }
+
+ APR_BUCKET_REMOVE(e);
+ APR_BRIGADE_INSERT_TAIL(bbOut, e);
+
+ outbytes += len;
+
+ continue;
+
+ }
+
+ /*
+ * Slow path.
+ *
+ * We need to read ahead at least one boundary worth of data so
+ * we can search across the bucket edges.
+ */
+ else {
+
+ apr_size_t off = 0;
+
+ /* find all definite non matches */
+ while (len) {
+ if (!strncmp(str + off, boundary, len)) {
+
+ if (off) {
+
+ apr_bucket_split(e, off);
+ APR_BUCKET_REMOVE(e);
+ APR_BRIGADE_INSERT_TAIL(bbOut, e);
+
+ e = APR_BRIGADE_FIRST(bbIn);
+ }
+
+ inbytes -= off;
+
+ goto skip;
+ }
+ off++;
+ len--;
+ }
+
+ APR_BUCKET_REMOVE(e);
+ APR_BRIGADE_INSERT_TAIL(bbOut, e);
+ continue;
+
+ }
+
+ /*
+ * If we reach skip, it means the bucket in e is:
+ *
+ * - shorter than the boundary
+ * - matches the boundary up to the bucket length
+ * - might match more buckets
+ *
+ * Read further buckets and check whether the boundary matches all
+ * the way to the end. If so, we have a match. If no match, shave off
+ * one byte and continue round to try again.
+ */
+skip:
+
+ for (next = APR_BUCKET_NEXT(e);
+ inbytes < boundary_len && next != APR_BRIGADE_SENTINEL(bbIn);
+ next = APR_BUCKET_NEXT(next)) {
+
+ const char *str;
+ apr_size_t off;
+ apr_size_t len;
+
+ rv = apr_bucket_read(next, &str, &len, block);
+
+ if (rv != APR_SUCCESS) {
+ return rv;
+ }
+
+ off = boundary_len - inbytes;
+
+ if (len > off) {
+
+ /* not a match, bail out */
+ if (strncmp(str, boundary + inbytes, off)) {
+ break;
+ }
+
+ /* a match! remove the boundary and return */
+ apr_bucket_split(next, off);
+
+ e = APR_BUCKET_NEXT(next);
+
+ for (prev = APR_BRIGADE_FIRST(bbIn);
+ prev != e;
+ prev = APR_BRIGADE_FIRST(bbIn)) {
+
+ apr_bucket_delete(prev);
+
+ }
+
+ return APR_SUCCESS;
+
+ }
+ if (len == off) {
+
+ /* not a match, bail out */
+ if (strncmp(str, boundary + inbytes, off)) {
+ break;
+ }
+
+ /* a match! remove the boundary and return */
+ e = APR_BUCKET_NEXT(next);
+
+ for (prev = APR_BRIGADE_FIRST(bbIn);
+ prev != e;
+ prev = APR_BRIGADE_FIRST(bbIn)) {
+
+ apr_bucket_delete(prev);
+
+ }
+
+ return APR_SUCCESS;
+
+ }
+ else if (len) {
+
+ /* not a match, bail out */
+ if (strncmp(str, boundary + inbytes, len)) {
+ break;
+ }
+
+ /* still hope for a match */
+ inbytes += len;
+ }
+
+ }
+
+ /*
+ * If we reach this point, the bucket e did not match the boundary
+ * in the subsequent buckets.
+ *
+ * Bump one byte off, and loop round to search again.
+ */
+ apr_bucket_split(e, 1);
+ APR_BUCKET_REMOVE(e);
+ APR_BRIGADE_INSERT_TAIL(bbOut, e);
+
+ outbytes++;
+
+ }
+
+ return APR_INCOMPLETE;
+}
+
APR_DECLARE(apr_status_t) apr_brigade_to_iovec(apr_bucket_brigade *b,
struct iovec *vec, int *nvec)
Modified: apr/apr/trunk/include/apr_buckets.h
URL: http://svn.apache.org/viewvc/apr/apr/trunk/include/apr_buckets.h?rev=1894380&r1=1894379&r2=1894380&view=diff
==============================================================================
--- apr/apr/trunk/include/apr_buckets.h (original)
+++ apr/apr/trunk/include/apr_buckets.h Tue Oct 19 14:30:37 2021
@@ -53,6 +53,11 @@ extern "C" {
/** default bucket buffer size - 8KB minus room for memory allocator headers */
#define APR_BUCKET_BUFF_SIZE 8000
+/** if passed to apr_brigade_split_boundary(), the string length will
+ * be calculated
+ */
+#define APR_BUCKETS_STRING -1
+
/** Determines how a bucket or brigade should be read */
typedef enum {
APR_BLOCK_READ, /**< block until data becomes available */
@@ -791,6 +796,38 @@ APR_DECLARE(apr_status_t) apr_brigade_sp
__attribute__((nonnull(1,2)));
/**
+ * Split a brigade based on the provided boundary, or metadata buckets,
+ * whichever are encountered first.
+ *
+ * If the boundary is found, all buckets prior to the boundary are passed
+ * into bbOut, and APR_SUCCESS is returned.
+ *
+ * If a metadata bucket is found, or if the boundary is not found within
+ * the limit specified by maxbytes, all prior buckets are passed into bbOut,
+ * and APR_INCOMPLETE is returned.
+ *
+ * Any partial matches at the end of a bucket will be held back
+ * If the boundary is NULL or the empty string, APR_EINVAL is returned.
+ *
+ * If an error is encountered, the APR error code will be returned.
+ *
+ * @param bbOut The bucket brigade that will have the LF line appended to.
+ * @param bbIn The input bucket brigade to search for a LF-line.
+ * @param block The blocking mode to be used to split the line.
+ * @param boundary The boundary string.
+ * @param boundary_len The length of the boundary string. If set to
+ * APR_BUCKETS_STRING, the length will be calculated.
+ * @param maxbytes The maximum bytes to read.
+ */
+APR_DECLARE(apr_status_t) apr_brigade_split_boundary(apr_bucket_brigade *bbOut,
+ apr_bucket_brigade *bbIn,
+ apr_read_type_e block,
+ const char *boundary,
+ apr_size_t boundary_len,
+ apr_off_t maxbytes)
+ __attribute__((nonnull(1,2)));
+
+/**
* Create an iovec of the elements in a bucket_brigade... return number
* of elements used. This is useful for writing to a file or to the
* network efficiently.
Modified: apr/apr/trunk/test/testbuckets.c
URL: http://svn.apache.org/viewvc/apr/apr/trunk/test/testbuckets.c?rev=1894380&r1=1894379&r2=1894380&view=diff
==============================================================================
--- apr/apr/trunk/test/testbuckets.c (original)
+++ apr/apr/trunk/test/testbuckets.c Tue Oct 19 14:30:37 2021
@@ -209,6 +209,62 @@ static void test_splitline(abts_case *tc
apr_bucket_alloc_destroy(ba);
}
+static void test_splitboundary(abts_case *tc, void *data)
+{
+ apr_bucket_alloc_t *ba = apr_bucket_alloc_create(p);
+ apr_bucket_brigade *bin, *bout;
+
+ /* fast path */
+ bin = make_simple_brigade(ba, "quick brown fox",
+ " jumped over the lazy dog");
+ bout = apr_brigade_create(p, ba);
+
+ APR_ASSERT_SUCCESS(tc, "split boundary",
+ apr_brigade_split_boundary(bout, bin,
+ APR_BLOCK_READ, "brown",
+ APR_BUCKETS_STRING, 100));
+
+ flatten_match(tc, "split boundary", bout, "quick ");
+ flatten_match(tc, "remainder", bin, " fox jumped over the lazy dog");
+
+ apr_brigade_destroy(bout);
+ apr_brigade_destroy(bin);
+
+ /* slow path */
+ bin = make_simple_brigade(ba, "quick brown fox jum",
+ "ped over the lazy dog");
+ bout = apr_brigade_create(p, ba);
+
+ APR_ASSERT_SUCCESS(tc, "split boundary",
+ apr_brigade_split_boundary(bout, bin,
+ APR_BLOCK_READ, "jumped",
+ APR_BUCKETS_STRING, 100));
+
+ flatten_match(tc, "split boundary", bout, "quick brown fox ");
+ flatten_match(tc, "remainder", bin, " over the lazy dog");
+
+ apr_brigade_destroy(bout);
+ apr_brigade_destroy(bin);
+
+ /* not found */
+ bin = make_simple_brigade(ba, "quick brown fox jum",
+ "ped over the lazy dog");
+ bout = apr_brigade_create(p, ba);
+
+ ABTS_ASSERT(tc, "split boundary",
+ apr_brigade_split_boundary(bout, bin,
+ APR_BLOCK_READ, "jumping",
+ APR_BUCKETS_STRING, 100) == APR_INCOMPLETE);
+
+ flatten_match(tc, "split boundary", bout, "quick brown fox jumped over the lazy dog");
+ flatten_match(tc, "remainder", bin, "");
+
+ apr_brigade_destroy(bout);
+ apr_brigade_destroy(bin);
+
+ apr_bucket_alloc_destroy(ba);
+}
+
/* Test that bucket E has content EDATA of length ELEN. */
static void test_bucket_content(abts_case *tc,
apr_bucket *e,
@@ -521,6 +577,7 @@ abts_suite *testbuckets(abts_suite *suit
abts_run_test(suite, test_split, NULL);
abts_run_test(suite, test_bwrite, NULL);
abts_run_test(suite, test_splitline, NULL);
+ abts_run_test(suite, test_splitboundary, NULL);
abts_run_test(suite, test_splits, NULL);
abts_run_test(suite, test_insertfile, NULL);
abts_run_test(suite, test_manyfile, NULL);
Re: svn commit: r1894380 - in /apr/apr/trunk: buckets/apr_brigade.c
include/apr_buckets.h test/testbuckets.c
Posted by Yann Ylavic <yl...@gmail.com>.
On Tue, Oct 19, 2021 at 4:31 PM <mi...@apache.org> wrote:
>
> --- apr/apr/trunk/include/apr_buckets.h (original)
> +++ apr/apr/trunk/include/apr_buckets.h Tue Oct 19 14:30:37 2021
> @@ -53,6 +53,11 @@ extern "C" {
> /** default bucket buffer size - 8KB minus room for memory allocator headers */
> #define APR_BUCKET_BUFF_SIZE 8000
>
> +/** if passed to apr_brigade_split_boundary(), the string length will
> + * be calculated
> + */
> +#define APR_BUCKETS_STRING -1
Maybe (apr_size_t)-1 ?
Regards;
Yann.
Re: svn commit: r1894380 - in /apr/apr/trunk: buckets/apr_brigade.c
include/apr_buckets.h test/testbuckets.c
Posted by Yann Ylavic <yl...@gmail.com>.
On Wed, Oct 20, 2021 at 11:01 PM Graham Leggett <mi...@sharp.fm> wrote:
>
> On 20 Oct 2021, at 10:43, Yann Ylavic <yl...@gmail.com> wrote:
>
>> apr_strnstr() maybe, strnstr() is non-standard AFAICT and possibly not
>> available on all platforms (Windows)?
>
> This needs to be memmem really, as the boundary isn’t always a string.
+1
>
> Memmem is non portable and old versions are buggy. Is there license compatibility to use this code?
>
> https://cvsweb.openbsd.org/src/lib/libc/string/memmem.c?rev=1.5
It's BSD license probably OK, otherwise there is apreq_index() here:
https://github.com/apache/apreq/blob/trunk/library/util.c#L92
Regards;
Yann.
Re: svn commit: r1894380 - in /apr/apr/trunk: buckets/apr_brigade.c
include/apr_buckets.h test/testbuckets.c
Posted by Ruediger Pluem <rp...@apache.org>.
On 10/20/21 11:01 PM, Graham Leggett wrote:
> On 20 Oct 2021, at 10:43, Yann Ylavic <yl...@gmail.com> wrote:
>
>> apr_strnstr() maybe, strnstr() is non-standard AFAICT and possibly not
>> available on all platforms (Windows)?
>
> This needs to be memmem really, as the boundary isn’t always a string.
But I guess in this case you need to replace strncmp with memcmp as well, correct?
Regards
Rüdiger
Re: svn commit: r1894380 - in /apr/apr/trunk: buckets/apr_brigade.c include/apr_buckets.h test/testbuckets.c
Posted by Graham Leggett <mi...@sharp.fm>.
On 20 Oct 2021, at 10:43, Yann Ylavic <yl...@gmail.com> wrote:
> apr_strnstr() maybe, strnstr() is non-standard AFAICT and possibly not
> available on all platforms (Windows)?
This needs to be memmem really, as the boundary isn’t always a string.
Memmem is non portable and old versions are buggy. Is there license compatibility to use this code?
https://cvsweb.openbsd.org/src/lib/libc/string/memmem.c?rev=1.5
>
>> +
>> + /* definitely found it, we leave */
>> + if (pos != NULL) {
>> +
>> + off = pos - str;
>> +
>> + /* everything up to the boundary */
>> + if (off) {
>> +
>> + apr_bucket_split(e, off);
>> + APR_BUCKET_REMOVE(e);
>> + APR_BRIGADE_INSERT_TAIL(bbOut, e);
>> +
>> + e = APR_BRIGADE_FIRST(bbIn);
>> + }
>> +
>> + /* cut out the boundary */
>> + apr_bucket_split(e, boundary_len);
>> + apr_bucket_delete(e);
>> +
>> + return APR_SUCCESS;
>> + }
>> +
>> + /* any partial matches at the end? */
>> + leftover = boundary_len - 1;
>> + off = (len - leftover);
>
> Can't we fall through the below "else" slow path here? The code looks
> quite similar.
Let me look, as I recall the paths are separate to be clear.
>> + APR_BUCKET_REMOVE(e);
>> + APR_BRIGADE_INSERT_TAIL(bbOut, e);
>> + continue;
>
> "outbytes" not bumped?
Good catch.
>
>> +
>> + }
>> +
>> + /*
>> + * If we reach skip, it means the bucket in e is:
>> + *
>> + * - shorter than the boundary
>> + * - matches the boundary up to the bucket length
>> + * - might match more buckets
>> + *
>> + * Read further buckets and check whether the boundary matches all
>> + * the way to the end. If so, we have a match. If no match, shave off
>> + * one byte and continue round to try again.
>> + */
>> +skip:
>
> Below you read ahead to try to match the end of the boundary, and if
> not split one byte into bbOut before restarting the loop, which could
> result in a quite fragmented bbOut and is also what you almost did
> above already.
>
> Couldn't we instead save the partially matching bucket(s) in a
> temporary brigade (provided by the caller) and restart the loop with
> the more effective [apr_]strnstr() match (at boundary+off)?
The input brigade is our temporary brigade. Instead of shaving off one on the bucket, we could keep a counter to just skip one (extra) byte on the next go round.
Regards,
Graham
—
Re: svn commit: r1894380 - in /apr/apr/trunk: buckets/apr_brigade.c
include/apr_buckets.h test/testbuckets.c
Posted by Yann Ylavic <yl...@gmail.com>.
For instance there is [1] in apreq that also splits a brigade on a boundary.
[1] https://github.com/apache/apreq/blob/trunk/library/parser_multipart.c#L112
Regards;
Yann.
On Wed, Oct 20, 2021 at 11:43 AM Yann Ylavic <yl...@gmail.com> wrote:
>
> On Tue, Oct 19, 2021 at 4:31 PM <mi...@apache.org> wrote:
> >
> > +APR_DECLARE(apr_status_t) apr_brigade_split_boundary(apr_bucket_brigade *bbOut,
> > + apr_bucket_brigade *bbIn,
> > + apr_read_type_e block,
> > + const char *boundary,
> > + apr_size_t boundary_len,
> > + apr_off_t maxbytes)
> > +{
> []
> > + /*
> > + * Fast path.
> > + *
> > + * If we have at least one boundary worth of data, do an optimised
> > + * substring search for the boundary, and split quickly if found.
> > + */
> > + if (len >= boundary_len) {
> > +
> > + apr_size_t off;
> > + apr_size_t leftover;
> > +
> > + pos = strnstr(str, boundary, len);
>
> apr_strnstr() maybe, strnstr() is non-standard AFAICT and possibly not
> available on all platforms (Windows)?
>
> > +
> > + /* definitely found it, we leave */
> > + if (pos != NULL) {
> > +
> > + off = pos - str;
> > +
> > + /* everything up to the boundary */
> > + if (off) {
> > +
> > + apr_bucket_split(e, off);
> > + APR_BUCKET_REMOVE(e);
> > + APR_BRIGADE_INSERT_TAIL(bbOut, e);
> > +
> > + e = APR_BRIGADE_FIRST(bbIn);
> > + }
> > +
> > + /* cut out the boundary */
> > + apr_bucket_split(e, boundary_len);
> > + apr_bucket_delete(e);
> > +
> > + return APR_SUCCESS;
> > + }
> > +
> > + /* any partial matches at the end? */
> > + leftover = boundary_len - 1;
> > + off = (len - leftover);
>
> Can't we fall through the below "else" slow path here? The code looks
> quite similar.
>
> > +
> > + while (leftover) {
> > + if (!strncmp(str + off, boundary, leftover)) {
> > +
> > + if (off) {
> > +
> > + apr_bucket_split(e, off);
> > + APR_BUCKET_REMOVE(e);
> > + APR_BRIGADE_INSERT_TAIL(bbOut, e);
> > +
> > + e = APR_BRIGADE_FIRST(bbIn);
> > + }
> > +
> > + outbytes += off;
> > + inbytes -= off;
> > +
> > + goto skip;
> > + }
> > + off++;
> > + leftover--;
> > + }
> > +
> > + APR_BUCKET_REMOVE(e);
> > + APR_BRIGADE_INSERT_TAIL(bbOut, e);
> > +
> > + outbytes += len;
> > +
> > + continue;
> > +
> > + }
> > +
> > + /*
> > + * Slow path.
> > + *
> > + * We need to read ahead at least one boundary worth of data so
> > + * we can search across the bucket edges.
> > + */
> > + else {
> > +
> > + apr_size_t off = 0;
> > +
> > + /* find all definite non matches */
> > + while (len) {
> > + if (!strncmp(str + off, boundary, len)) {
> > +
> > + if (off) {
> > +
> > + apr_bucket_split(e, off);
> > + APR_BUCKET_REMOVE(e);
> > + APR_BRIGADE_INSERT_TAIL(bbOut, e);
> > +
> > + e = APR_BRIGADE_FIRST(bbIn);
> > + }
> > +
> > + inbytes -= off;
> > +
> > + goto skip;
> > + }
> > + off++;
> > + len--;
> > + }
> > +
> > + APR_BUCKET_REMOVE(e);
> > + APR_BRIGADE_INSERT_TAIL(bbOut, e);
> > + continue;
>
> "outbytes" not bumped?
>
> > +
> > + }
> > +
> > + /*
> > + * If we reach skip, it means the bucket in e is:
> > + *
> > + * - shorter than the boundary
> > + * - matches the boundary up to the bucket length
> > + * - might match more buckets
> > + *
> > + * Read further buckets and check whether the boundary matches all
> > + * the way to the end. If so, we have a match. If no match, shave off
> > + * one byte and continue round to try again.
> > + */
> > +skip:
>
> Below you read ahead to try to match the end of the boundary, and if
> not split one byte into bbOut before restarting the loop, which could
> result in a quite fragmented bbOut and is also what you almost did
> above already.
>
> Couldn't we instead save the partially matching bucket(s) in a
> temporary brigade (provided by the caller) and restart the loop with
> the more effective [apr_]strnstr() match (at boundary+off)?
>
> > +
> > + for (next = APR_BUCKET_NEXT(e);
> > + inbytes < boundary_len && next != APR_BRIGADE_SENTINEL(bbIn);
> > + next = APR_BUCKET_NEXT(next)) {
> > +
> > + const char *str;
> > + apr_size_t off;
> > + apr_size_t len;
> > +
> > + rv = apr_bucket_read(next, &str, &len, block);
> > +
> > + if (rv != APR_SUCCESS) {
> > + return rv;
> > + }
> > +
> > + off = boundary_len - inbytes;
> > +
> > + if (len > off) {
> > +
> > + /* not a match, bail out */
> > + if (strncmp(str, boundary + inbytes, off)) {
> > + break;
> > + }
> > +
> > + /* a match! remove the boundary and return */
> > + apr_bucket_split(next, off);
> > +
> > + e = APR_BUCKET_NEXT(next);
> > +
> > + for (prev = APR_BRIGADE_FIRST(bbIn);
> > + prev != e;
> > + prev = APR_BRIGADE_FIRST(bbIn)) {
> > +
> > + apr_bucket_delete(prev);
> > +
> > + }
> > +
> > + return APR_SUCCESS;
> > +
> > + }
> > + if (len == off) {
> > +
> > + /* not a match, bail out */
> > + if (strncmp(str, boundary + inbytes, off)) {
> > + break;
> > + }
> > +
> > + /* a match! remove the boundary and return */
> > + e = APR_BUCKET_NEXT(next);
> > +
> > + for (prev = APR_BRIGADE_FIRST(bbIn);
> > + prev != e;
> > + prev = APR_BRIGADE_FIRST(bbIn)) {
> > +
> > + apr_bucket_delete(prev);
> > +
> > + }
> > +
> > + return APR_SUCCESS;
> > +
> > + }
> > + else if (len) {
> > +
> > + /* not a match, bail out */
> > + if (strncmp(str, boundary + inbytes, len)) {
> > + break;
> > + }
> > +
> > + /* still hope for a match */
> > + inbytes += len;
> > + }
> > +
> > + }
> > +
> > + /*
> > + * If we reach this point, the bucket e did not match the boundary
> > + * in the subsequent buckets.
> > + *
> > + * Bump one byte off, and loop round to search again.
> > + */
> > + apr_bucket_split(e, 1);
> > + APR_BUCKET_REMOVE(e);
> > + APR_BRIGADE_INSERT_TAIL(bbOut, e);
> > +
> > + outbytes++;
> > +
> > + }
> > +
> > + return APR_INCOMPLETE;
> > +}
>
>
> Regards;
> Yann.
Re: svn commit: r1894380 - in /apr/apr/trunk: buckets/apr_brigade.c
include/apr_buckets.h test/testbuckets.c
Posted by Yann Ylavic <yl...@gmail.com>.
On Tue, Oct 19, 2021 at 4:31 PM <mi...@apache.org> wrote:
>
> +APR_DECLARE(apr_status_t) apr_brigade_split_boundary(apr_bucket_brigade *bbOut,
> + apr_bucket_brigade *bbIn,
> + apr_read_type_e block,
> + const char *boundary,
> + apr_size_t boundary_len,
> + apr_off_t maxbytes)
> +{
[]
> + /*
> + * Fast path.
> + *
> + * If we have at least one boundary worth of data, do an optimised
> + * substring search for the boundary, and split quickly if found.
> + */
> + if (len >= boundary_len) {
> +
> + apr_size_t off;
> + apr_size_t leftover;
> +
> + pos = strnstr(str, boundary, len);
apr_strnstr() maybe, strnstr() is non-standard AFAICT and possibly not
available on all platforms (Windows)?
> +
> + /* definitely found it, we leave */
> + if (pos != NULL) {
> +
> + off = pos - str;
> +
> + /* everything up to the boundary */
> + if (off) {
> +
> + apr_bucket_split(e, off);
> + APR_BUCKET_REMOVE(e);
> + APR_BRIGADE_INSERT_TAIL(bbOut, e);
> +
> + e = APR_BRIGADE_FIRST(bbIn);
> + }
> +
> + /* cut out the boundary */
> + apr_bucket_split(e, boundary_len);
> + apr_bucket_delete(e);
> +
> + return APR_SUCCESS;
> + }
> +
> + /* any partial matches at the end? */
> + leftover = boundary_len - 1;
> + off = (len - leftover);
Can't we fall through the below "else" slow path here? The code looks
quite similar.
> +
> + while (leftover) {
> + if (!strncmp(str + off, boundary, leftover)) {
> +
> + if (off) {
> +
> + apr_bucket_split(e, off);
> + APR_BUCKET_REMOVE(e);
> + APR_BRIGADE_INSERT_TAIL(bbOut, e);
> +
> + e = APR_BRIGADE_FIRST(bbIn);
> + }
> +
> + outbytes += off;
> + inbytes -= off;
> +
> + goto skip;
> + }
> + off++;
> + leftover--;
> + }
> +
> + APR_BUCKET_REMOVE(e);
> + APR_BRIGADE_INSERT_TAIL(bbOut, e);
> +
> + outbytes += len;
> +
> + continue;
> +
> + }
> +
> + /*
> + * Slow path.
> + *
> + * We need to read ahead at least one boundary worth of data so
> + * we can search across the bucket edges.
> + */
> + else {
> +
> + apr_size_t off = 0;
> +
> + /* find all definite non matches */
> + while (len) {
> + if (!strncmp(str + off, boundary, len)) {
> +
> + if (off) {
> +
> + apr_bucket_split(e, off);
> + APR_BUCKET_REMOVE(e);
> + APR_BRIGADE_INSERT_TAIL(bbOut, e);
> +
> + e = APR_BRIGADE_FIRST(bbIn);
> + }
> +
> + inbytes -= off;
> +
> + goto skip;
> + }
> + off++;
> + len--;
> + }
> +
> + APR_BUCKET_REMOVE(e);
> + APR_BRIGADE_INSERT_TAIL(bbOut, e);
> + continue;
"outbytes" not bumped?
> +
> + }
> +
> + /*
> + * If we reach skip, it means the bucket in e is:
> + *
> + * - shorter than the boundary
> + * - matches the boundary up to the bucket length
> + * - might match more buckets
> + *
> + * Read further buckets and check whether the boundary matches all
> + * the way to the end. If so, we have a match. If no match, shave off
> + * one byte and continue round to try again.
> + */
> +skip:
Below you read ahead to try to match the end of the boundary, and if
not split one byte into bbOut before restarting the loop, which could
result in a quite fragmented bbOut and is also what you almost did
above already.
Couldn't we instead save the partially matching bucket(s) in a
temporary brigade (provided by the caller) and restart the loop with
the more effective [apr_]strnstr() match (at boundary+off)?
> +
> + for (next = APR_BUCKET_NEXT(e);
> + inbytes < boundary_len && next != APR_BRIGADE_SENTINEL(bbIn);
> + next = APR_BUCKET_NEXT(next)) {
> +
> + const char *str;
> + apr_size_t off;
> + apr_size_t len;
> +
> + rv = apr_bucket_read(next, &str, &len, block);
> +
> + if (rv != APR_SUCCESS) {
> + return rv;
> + }
> +
> + off = boundary_len - inbytes;
> +
> + if (len > off) {
> +
> + /* not a match, bail out */
> + if (strncmp(str, boundary + inbytes, off)) {
> + break;
> + }
> +
> + /* a match! remove the boundary and return */
> + apr_bucket_split(next, off);
> +
> + e = APR_BUCKET_NEXT(next);
> +
> + for (prev = APR_BRIGADE_FIRST(bbIn);
> + prev != e;
> + prev = APR_BRIGADE_FIRST(bbIn)) {
> +
> + apr_bucket_delete(prev);
> +
> + }
> +
> + return APR_SUCCESS;
> +
> + }
> + if (len == off) {
> +
> + /* not a match, bail out */
> + if (strncmp(str, boundary + inbytes, off)) {
> + break;
> + }
> +
> + /* a match! remove the boundary and return */
> + e = APR_BUCKET_NEXT(next);
> +
> + for (prev = APR_BRIGADE_FIRST(bbIn);
> + prev != e;
> + prev = APR_BRIGADE_FIRST(bbIn)) {
> +
> + apr_bucket_delete(prev);
> +
> + }
> +
> + return APR_SUCCESS;
> +
> + }
> + else if (len) {
> +
> + /* not a match, bail out */
> + if (strncmp(str, boundary + inbytes, len)) {
> + break;
> + }
> +
> + /* still hope for a match */
> + inbytes += len;
> + }
> +
> + }
> +
> + /*
> + * If we reach this point, the bucket e did not match the boundary
> + * in the subsequent buckets.
> + *
> + * Bump one byte off, and loop round to search again.
> + */
> + apr_bucket_split(e, 1);
> + APR_BUCKET_REMOVE(e);
> + APR_BRIGADE_INSERT_TAIL(bbOut, e);
> +
> + outbytes++;
> +
> + }
> +
> + return APR_INCOMPLETE;
> +}
Regards;
Yann.