httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Greg Stein <gst...@lyra.org>
Subject code chunks for filter challenge
Date Thu, 29 Jun 2000 14:06:41 GMT
Okee dokee... so I got a second wind and tackled this. I don't have a sample
module because the usage of this stuff is pretty easy. See below for the
actual code chunks, but here is what a module would do:

typedef struct {
    ap_setaside_t sa;
} my_ctx;

void my_callback(ap_filter_t *filter, ap_bucket_t *bucket)
{
    my_ctx *ctx = filter->ctx;

    ... process bucket ...
    if (dont_send_yet)
        ap_setaside_bucket(&ctx->sa, bucket, filter->r->pool);
    else {
        ap_table_set(filter->r->headers_out, "foo", "bar");
        ap_lputsetaside(filter, &ctx->sa);
	ap_clear_setaside(&ctx->sa);
    }
}

Note that the filter performs no direct allocations. ap_setaside_bucket()
certainly can, but only when data lifetimes need to change.

The zero-alloc behavior comes from the ap_selfdef_t type ("self-defined
storage"). This bucket type determines its own lifetime by virtue of
carrying around a (sub)pool of its own. ap_setaside_bucket() can then string
these babies together, until ap_lputsetaside() is called.

If other bucket types are passed to ap_setaside_bucket(), then it will make
the necessary copy to ensure that it will live past the function-return.

If too much memory data is set aside, then it is spilled to a temp file.
File buckets do not trigger the memory threshold.

ap_setaside_bucket() allocates memory only when necessary. If data gets
spilled, then it will have a sub-pool to hold ap_selfdef_t structures and
ap_file_t structures. Note that the number of these structures is no more
than 2n+1, where n is the number of files placed into the content stream.
(reducing this count would imply copying file contents, whatever algorithm
may be chosen)

The ap_lputsetaside() function will pass the elements of a setaside
structure down to the next filter. Where possible, it will pass a SELFDEF so
the next filter can grab the sucker intact without copying.


To help understand this stuff, I'll detail a bit about the ap_selfdef_t
structure... it has three types:

1) AP_SELFDEF_PTRLEN: ->pool will be set and contains the ap_selfdef_t
   itself and the data referenced by ->buf (and ->len)

2) AP_SELFDEF_FILE: ->pool will be NULL, the ap_selfdef_t is allocated in an
   unknown pool. ->file refers to the file in question (starting at the
   current file position), ->flen says how many bytes from there

3) AP_SELFDEF_SPILL: all fields empty except for ->len. This length says how
   many bytes to consume from the spill file. If you scan from the start of
   an ap_setaside_t structure, the _SPILL elements are layed out
   sequentially in the spill file. This ap_selfdef_t is allocated in the
   ap_setaside_t.pool

The ap_setaside_t simply contains a head/tail pointer for the selfdef
structures, along with (possibly) a private pool and (possibly) a spill
file. Once ->spill is set, then all memory-based content is dropped into the
spill file.

Note that the chain referenced by setaside.head will contain _PTRLEN *or*
_SPILL elements. Never both. The former is before spilling occurs, the
latter after spilling. _FILE will occur in either state.

When an ap_selfdef_t is placed into an ap_setaside_t, and it is a _FILE,
then the file will be dup'd into the sa->pool. A new ap_selfdef_t is
allocated in the sa->pool (because we don't know where the original was
allocated, so we can't determine its lifetime).

Note: that is a policy decision: a _FILE selfdef does not create a whole
pool just to hold the darn file. It certainly could, but I punted that.

_SPILL selfdefs only occur in a setaside structure and are allocated from
the sa->pool.

-----------

whew. It does sound messy, but that is simply because we are dealing with
data that can have unknown lifetimes. We need to properly manage each of
those items. If the data *does* have a known lifetime (AP_BUCKET_SELFDEF
with an AP_SELFDEF_PTRLEN), then we just drop the thing into the setaside
buffer. Piece of cake, no copying. When that thing is pulled out to be sent
to the next filter, it is sent in its original form which allows the next
filter to set it aside, too.

If you ignore this prose, and just look at the new data structures
(ap_selfdef_t and ap_setaside_t), then you can build up the logic from there.

All the guts of the mechanism is in ap_setaside_bucket().

-----------

Zero-copy path, assuming no spill:

(sa refers to an ap_setaside_t, sd refers to an ap_selfdef_t)

(1) my_callback is called with an AP_BUCKET_SELFDEF (sd) referring to an
AP_SELFDEF_PTRLEN. <sd> is directly chained into <sa>. Repeat. [ follow the
code path in ap_setaside_bucket() to verify no allocs ]

ap_lputsetaside() is called. It loops over the selfdef structures. If the
next filter uses bucket callbacks, then an AP_BUCKET_SELFDEF is built which
refers to this sd. The callback is called. This is the same state as point
(1), so induction shows we can call N filters without copying. At the
bottom, (internally) ap_lwrite() is called with the data which is passed to
ap_bwrite() with no copies.

-----------

If a spill occurs, and *only* content data is present (no files in the
content stream), then all the data will be placed into the sa->spill file
and there will be a single _SPILL selfdata (no matter how many invocations
to the callback occurred; the writes are coalesced)

ap_lputsetaside() will call ap_lsendfile() for the whole spill file. Of
course, this can map into the platform's sendfile().

-----------

When files are present in the content stream, things get a bit more fun, but
it is pretty straight-forward. ap_selfdef_t (_FILE) elements get linked. At
output time, each of the files are delivered via ap_lsendfile().
[ interleaved with regular content data ]


Okay... enough discussion for now. Below, I've appended the new functions
and types. This stuff compiles, but I haven't explicitly tested it (since
we're only going for theory here).

Here is a quick summary of the posted requireements, and a quick answer:

1) entire response must be able to be held by one module (with spill)
   => MET. ap_setaside_t and friends manage this fine

2) no memory allocated out of r->pool
   => MET, with caveats.

      ap_file_t structures are allocated. some ap_selfdef_t are allocated
      to manage lifetimes of data.
      
      this requirement is a bit too absolute given the variety of inputs to
      the filter system (e.g., ap_rwrite, ap_send_fd, ap_rprintf). for the
      case in question: where a SELFDEF is passed, no allocations occur. a
      bit happens when spill occurs. etc.
      
      I expect discussion to focus here.

3) the position in the filter chain should not matter. the algorithm should
   not disable downstream filters from doing the same thing.
   => MET. a SELFDEF will be passed to the next filter if it uses buckets.

4) write as a bucket and as a char *
   => N/A per earlier discussion

5) example filter doesn't have to modify anything; no allocation except for
   structures to refer to the content.
   => MET.
   
      note this req't allows some types of allocation. no biggy, as I avoid
      allocations in the code. but interesting to point out in light of (2)

6) do not copy data that is not modified.
   => MET, with caveats.
      
      data must be copied to account for changing lifetimes. If a SELFDEF is
      fed into the chain (or pops up inside the chain), then copies will no
      longer occur.


Cheers,
-g

-- 
Greg Stein, http://www.lyra.org/


typedef enum {
    AP_SELFDEF_PTRLEN,
    AP_SELFDEF_FILE,
    AP_SELFDEF_SPILL
} ap_selfdef_type;

struct ap_selfdef_t {
    int filter_owns;

    ap_pool_t *pool;

    ap_selfdef_type type;

    const char *buf;            /* AP_SELFDEF_PTRLEN */
    ap_size_t len;              /* AP_SELFDEF_PTRLEN, _SPILL */

    ap_file_t *file;            /* AP_SELFDEF_FILE */
    ap_ssize_t flen;            /* AP_SELFDEF_FILE */

    struct ap_selfdef_t *next;
};

struct ap_setaside_t {
    ap_size_t total_mem;
    ap_selfdef_t *head;
    ap_selfdef_t *tail;

    ap_pool_t *pool;
    ap_file_t *spill;
};

API_EXPORT(void) ap_setaside_bucket(ap_setaside_t *sa,
                                    const ap_bucket_t *bucket,
                                    ap_pool_t *pool);
API_EXPORT(void) ap_clear_setaside(ap_setaside_t *sa);

-------------------------------------------------------------------

API_EXPORT(void) ap_lputsetaside(ap_filter_t *filter, const ap_setaside_t *sa)
{
    ap_selfdef_t *scan;
    ap_selfdef_t *next;

    /* rewind the spill file, if present */
    if (sa->spill != NULL) {
        (void) ap_seek(sa->spill, APR_SET, 0);
    }

    for (scan = sa->head; scan != NULL; scan = next) {
        /* the <sa> no longer owns this if we are sending it */
        scan->filter_owns = 0;

        /* grab the next pointer. if somebody takes this item, they will
           probably change the value. */
        next = scan->next;

        switch (scan->type) {
        case AP_SELFDEF_PTRLEN:
        {
            ap_filter_t *f_next = filter->next;

            if (f_next != NULL && f_next->bucket_cb != NULL) {
                ap_bucket_t bucket = {
                    AP_BUCKET_SELFDEF, NULL, 0, NULL, NULL, NULL, 0, scan
                };
                (*f_next->bucket_cb)(f_next, &bucket);
            }
            else {
                /* send some bytes; not as optimal */
                ap_lwrite(filter, scan->buf, scan->len);
            }
            break;
        case AP_SELFDEF_FILE:
            /* send the file */
            ap_lsendfile(filter, scan->file, scan->flen);
            break;
        case AP_SELFDEF_SPILL:
            /* send (len) bytes out of the spill file */
            ap_lsendfile(filter, sa->spill, scan->len);
            break;
        default:
            /* ### error... */
            ap_assert(0);
            return;
        }
    }
}

-------------------------------------------------------------------

API_EXPORT(void) ap_setaside_bucket(ap_setaside_t *sa,
                                    const ap_bucket_t *bucket,
                                    ap_pool_t *request_pool)
{
    ap_ssize_t needed;
    ap_pool_t *subpool = NULL;
    ap_pool_t *fmtpool = NULL;
    ap_array_header_t *strs;
    const char *s;
    ap_selfdef_t *sd;

    /* a selfdef has its own pool; for the others, we will need one */
    if (bucket->type != AP_BUCKET_SELFDEF && sa->pool == NULL) {
        (void) ap_create_pool(&sa->pool, request_pool);
    }

    /* default: format directly into the spill pool */
    fmtpool = sa->pool;

    if (sa->spill == NULL
        && (bucket->type == AP_BUCKET_STRINGS
            || bucket->type == AP_BUCKET_PRINTF)) {
        /* format into a new subpool; this data may be dumped to a spill
           file and the subpool will be destroyed */
        (void) ap_create_pool(&subpool, request_pool);
        fmtpool = subpool;
    }

    switch (bucket->type) {
    case AP_BUCKET_PTRLEN:
        needed = bucket->len;
        break;
    case AP_BUCKET_STRINGS:
    {
        va_list va = bucket->va;
        int i;
        char *s2;

        strs = ap_make_array(fmtpool, 5, sizeof(const char *));

        /* compute the total size */
        needed = 0;
        while (1) {
            s = va_arg(va, const char *);
            if (s == NULL)
                break;
            *(const char **)ap_push_array(strs) = s;
            needed += strlen(s);
        }

        /* concatenate them all together */
        s = s2 = ap_palloc(fmtpool, needed);
        for (i = 0; i < strs->nelts; ++i) {
            const char *s3 = ((const char **)strs->elts)[i];
            ap_size_t len = strlen(s3);
            memcpy(s2, s3, len);
            s2 += len;
        }
        break;
    }
    case AP_BUCKET_PRINTF:
        s = ap_pvsprintf(fmtpool, bucket->fmt, bucket->va);
        needed = strlen(s);
        break;
    case AP_BUCKET_FILE:
        needed = 0;
        break;
    case AP_BUCKET_SELFDEF:
        switch (bucket->selfdef->type) {
        case AP_SELFDEF_PTRLEN:
            needed = bucket->selfdef->len;
            break;
        case AP_SELFDEF_FILE:
            needed = 0;
            break;
        case AP_SELFDEF_SPILL:
        default:
            /* ### error... */
            ap_assert(0);
            return;
        }
        break;
    default:
        /* ### error... */
        ap_assert(0);
        return;
    }

    if (sa->spill == NULL) {
        sa->total_mem += needed;
        if (sa->total_mem > SPILL_THRESHOLD) {
            const char *fname;

            if (sa->pool == NULL) {
                (void) ap_create_pool(&sa->pool, request_pool);
            }

            fname = "/tmp/spill";       /* ### yah. right */
            (void) ap_open(&sa->spill, fname,
                           APR_WRITE | APR_CREATE | APR_EXCL | APR_DELONCLOSE,
                           APR_UREAD, sa->pool);

            /* ### walk sa, spilling data. must coalesce blocks. */

            /* ### fall thru to place data into spill areas */
        }
        else {
            if (bucket->type == AP_BUCKET_SELFDEF) {
                sd = bucket->selfdef;
                sd->filter_owns = 1;
            }
            else {
                /* PTRLEN buckets need a pool to copy the data into */
                if (bucket->type == AP_BUCKET_PTRLEN) {
                    (void) ap_create_pool(&fmtpool, request_pool);
                }

                /* for _FILE, fmtpool == sa->pool */
                sd = ap_pcalloc(fmtpool, sizeof(*sd));

                switch (bucket->type) {
                case AP_BUCKET_PTRLEN:
                    sd->pool = fmtpool;
                    sd->type = AP_SELFDEF_PTRLEN;
                    sd->buf = ap_pstrndup(sd->pool, bucket->buf, needed);
                    sd->len = needed;
                    break;
                case AP_BUCKET_STRINGS:
                case AP_BUCKET_PRINTF:
                    sd->pool = fmtpool;
                    sd->type = AP_SELFDEF_PTRLEN;
                    sd->buf = s;
                    sd->len = needed;
                    break;
                case AP_BUCKET_FILE:
                    sd->type = AP_SELFDEF_FILE;
                    /* dup the file into our pool */
                    (void) ap_dupfile(&sd->file, bucket->file, sa->pool);
                    sd->flen = bucket->flen;
                    break;
                }
            }

            if (sa->head == NULL) {
                sa->head = sa->tail = sd;
            }
            else {
                sa->tail->next = sd;
                sa->tail = sd;
            }

            /* done */
            return;
        }
    }

    /* data must be placed into the spill */

    /* append to the previous spill datum? */
    if (sa->tail != NULL && sa->tail->type == AP_SELFDEF_SPILL
        && (bucket->type == AP_BUCKET_PTRLEN
            || bucket->type == AP_BUCKET_STRINGS
            || bucket->type == AP_BUCKET_PRINTF
            || (bucket->type == AP_BUCKET_SELFDEF &&
                bucket->selfdef->type == AP_SELFDEF_PTRLEN))) {

        sa->tail->len += needed;
        switch (bucket->type) {
        case AP_BUCKET_PTRLEN:
            (void) ap_write(sa->spill, bucket->buf, &needed);
            break;
        case AP_BUCKET_STRINGS:
        case AP_BUCKET_PRINTF:
            (void) ap_write(sa->spill, s, &needed);
            break;
        case AP_BUCKET_SELFDEF:
            (void) ap_write(sa->spill, bucket->selfdef->buf, &needed);
            break;
        }

        /* trash the formatting pool (its contents were spilled) */
        if (fmtpool != sa->pool)
            ap_destroy_pool(fmtpool);
        return;
    }

    /* spill to a new datum */
    sd = ap_pcalloc(sa->pool, sizeof(*sd));

    switch (bucket->type) {
    case AP_BUCKET_PTRLEN:
        sd->type = AP_SELFDEF_SPILL;
        sd->len = needed;
        (void) ap_write(sa->spill, bucket->buf, &needed);
        break;
    case AP_BUCKET_STRINGS:
    case AP_BUCKET_PRINTF:
        sd->type = AP_SELFDEF_SPILL;
        sd->len = needed;
        (void) ap_write(sa->spill, s, &needed);
        break;
    case AP_BUCKET_FILE:
        sd->type = AP_SELFDEF_FILE;
        /* dup the file into our pool */
        (void) ap_dupfile(&sd->file, bucket->file, sa->pool);
        sd->flen = bucket->flen;
        break;
    case AP_BUCKET_SELFDEF:
        switch (bucket->selfdef->type) {
        case AP_SELFDEF_PTRLEN:
            sd->type = AP_SELFDEF_SPILL;
            sd->len = needed;
            (void) ap_write(sa->spill, bucket->selfdef->buf, &needed);
            break;
        case AP_SELFDEF_FILE:
            /*
            ** ### can we just take this selfdef (and set filter_owns)?
            ** ### specifically: is selfdef->pool set, holding this file?
            */
            sd->type = AP_SELFDEF_FILE;
            /* dup the file into our pool */
            (void) ap_dupfile(&sd->file, bucket->selfdef->file, sa->pool);
            sd->flen = bucket->selfdef->flen;
            break;
        }
        break;
    }

    if (sa->head == NULL) {
        sa->head = sa->tail = sd;
    }
    else {
        sa->tail->next = sd;
        sa->tail = sd;
    }

    /* trash the formatting pool (its contents were spilled) */
    if (fmtpool != sa->pool)
        ap_destroy_pool(fmtpool);
}

API_EXPORT(void) ap_clear_setaside(ap_setaside_t *sa)
{
    ap_selfdef_t *scan;
    ap_selfdef_t *next;

    for (scan = sa->head; scan != NULL; scan = next) {
        /* grab ->next before we blast the pool (which might hold *scan) */
        next = scan->next;

        /* do not blast the pool if somebody has taken it */
        if (!scan->filter_owns && scan->pool != NULL)
            ap_destroy_pool(scan->pool);
    }
    ap_destroy_pool(sa->pool);

    memset(sa, 0, sizeof(*sa));
}

Mime
View raw message