You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@httpd.apache.org by "Paul J. Reder" <re...@raleigh.ibm.com> on 2000/10/24 21:37:41 UTC
Mod_include design
I have been working on rewriting mod_include. I haven't posted anything here
because I thought I would have it done pretty soon, but I have seen several
posts of patches to get it working so I thought I should post some design
and status info.
Basically, as I understand it, mod_include needs to be fixed to handle SSI
tags that can span multiple buckets or, in worst case, multiple brigades.
The rest of the SSI processing (once the tag is obtained) seems to be ok.
In order to do this I am converting mod_include to be a state machine with
the state stored in the attached data structure in the filter ctx.
HIGH LEVEL DESIGN:
Buckets are parsed until the STARTING_SEQUENCE (or at least the first byte(s))
are found. Once the STARTING_SEQUENCE is found, buckets are set aside into
the ssi_brigade in ctx until the ENDING_SEQUENCE is found. The bucket containing
the first byte of the STARTING_SEQUENCE is split at the first byte. All buckets
up to the new split bucket are passed on.
If a partial STARTING_SEQUENCE is found at the end of a bucket, that bucket is split
and set aside. If the bytes in the next bucket do not continue to match the
STARTING_SEQUENCE the state machine is reset. The set aside buckets will be passed on.
Once the full SSI tag has been parsed and set aside, the tag is copied into a
single buffer for processing and all of the set aside buckets are released.
>From here on, processing of the SSI tag proceeds as before.
CURRENT STATUS:
I have rewritten the code that loops through buckets so that it now operates as
a state machine where the state is stored into f->ctx for use across brigade
invocations. mod_include is now able to operate not only across buckets within
a brigade, but across brigades as well.
I have written the code that handles the worst case scenario (one byte per bucket
with one bucket per brigade).
I am in the process of finishing the code to do the bucket splitting and set aside
management.
After that I need to write the code to walk the set aside buckets and copy the tag
into a buffer and release the buckets. Then test.
I will be writing a test filter to put in front of mod_include that will
do pathological things to brigades (like force the worst case scenario) so
that all of the boundary conditions can be tested in a controlled way.
I'm sorry this has taken me so long, but I have been out of the 2.0 loop for
a while and have had a lot to learn with all of the brigade and filter
code. I have been picking up steam over the past couple of days and hope to
have something working in the next couple of days. It would be very helpful if
I were allowed to finish this without dribs and drabs of patches to get this
piece or that piece fixed in the current version, it just means I need to manually
merge the parts of these patches that still apply into the rewritten code to keep
them in synch.
/****************************************************************************
* Used to keep context information during parsing of a request for SSI tags.
* This is especially useful if the tag stretches across multiple buckets or
* brigades. This keeps track of which buckets need to be replaced with the
* content generated by the SSI tag.
*
* state: PRE_HEAD - State prior to finding the first character of the
* STARTING_SEQUENCE. Next state is PARSE_HEAD.
* PARSE_HEAD - State entered once the first character of the
* STARTING_SEQUENCE is found and exited when the
* the full STARTING_SEQUENCE has been matched or
* a match failure occurs. Next state is PRE_HEAD
* or PARSE_TAG.
* PARSE_TAG - State entered once the STARTING sequence has been
* matched. It is exited when the first character in
* ENDING_SEQUENCE is found. Next state is PARSE_TAIL.
* PARSE_TAIL - State entered from PARSE_TAG state when the first
* character in ENDING_SEQUENCE is encountered. This
* state is exited when the ENDING_SEQUENCE has been
* completely matched, or when a match failure occurs.
* Next state is PARSE_TAG or PARSED.
* PARSED - State entered from PARSE_TAIL once the complete
* ENDING_SEQUENCE has been matched. The SSI tag is
* processed and the SSI buckets are replaced with the
* SSI content during this state.
* parse_pos: Current matched position within the STARTING_SEQUENCE or
* ENDING_SEQUENCE during the PARSE_HEAD and PARSE_TAIL states.
* This is especially useful when the sequence spans brigades.
* X_start_bucket: These point to the buckets containing the first character
* of the STARTING_SEQUENCE, the first non-whitespace
* character of the tag, and the first character in the
* ENDING_SEQUENCE (head_, tag_, and tail_ respectively).
* The buckets are kept intact until the PARSED state is
* reached, at which time the tag is consolidated and the
* buckets are released. The buckets that these point to
* have all been set aside in the ssi_tag_brigade (along
* with all of the intervening buckets).
* X_start_index: The index points within the specified bucket contents
* where the first character of the STARTING_SEQUENCE,
* the first non-whitespace character of the tag, and the
* first character in the ENDING_SEQUENCE can be found
* (head_, tag_, and tail_ respectively).
* combined_tag: Once the PARSED state is reached the tag is collected from
* the bucket(s) in the ssi_tag_brigade into this contiguous
* buffer. The buckets in the ssi_tag_brigade are released
* and the tag is processed.
* tag_length: The number of bytes in the actual tag (excluding the
* STARTING_SEQUENCE, leading and trailing whitespace,
* and ENDING_SEQUENCE). This length is computed as the
* buckets are parsed and set aside during the PARSE_TAG state.
* ssi_tag_brigade: The temporary brigade used by this filter to set aside
* the buckets containing parts of the ssi tag and headers.
*/
typedef struct include_filter_ctx {
enum state {PRE_HEAD, PARSE_HEAD, PARSE_TAG, PARSE_TAIL, PARSED};
apr_ssize_t parse_pos;
ap_bucket *head_start_bucket;
apr_ssize_t head_start_index;
ap_bucket *tag_start_bucket;
apr_ssize_t tag_start_index;
ap_bucket *tail_start_bucket;
apr_ssize_t tail_start_index;
char *combined_tag;
apr_ssize_t tag_length;
ap_bucket_brigade ssi_tag_brigade;
} include_ctx_t;
--
Paul J. Reder
-----------------------------------------------------------
"The strength of the Constitution lies entirely in the determination of each
citizen to defend it. Only if every single citizen feels duty bound to do
his share in this defense are the constitutional rights secure."
-- Albert Einstein
Re: Mod_include design
Posted by Greg Stein <gs...@lyra.org>.
On Thu, Nov 02, 2000 at 11:59:47AM -0800, rbb@covalent.net wrote:
>
> > But: it definitely depends on how bounded the size of a directive can be. I
> > mean, can a directive be 10k long? If it is bounded, say, to MAX_PATH + 200,
> > then we just put that buffer into the ctx and run with it.
>
> I wouldn't personally put it into the ctx, because this will all be done
> in a single call to the filter,
What do you mean? The directive can arrive over multiple (not single!) calls
to the filter. We can put a set-aside brigade into the context, or we can
alloc the buffer once and put it there (and copy stuff onto the end). It is
more efficient to copy from the brigade into the buffer, than to copy during
a set-aside, then copy again into a buffer.
> but yes if the directive length is
> bounded, we could copy. Unfortunately, I don't think the length is
> bounded, so I think we need to be able to deal with partial tags in a
> bucket.
Well, we need to see the grammar to determine the bound. At a minimum, the
tags are bounded and I would guess certain arguments/tokens are bounded;
these can/should use a buffer to hold them during parsing.
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
Re: Mod_include design
Posted by "Paul J. Reder" <re...@raleigh.ibm.com>.
Wow, I'm a little overwhelmed here. After a dearth of comments or input I took
my eyes off my mail for 1/2 a day and get flooded. Please allow me to
apologize up front for the length of this post. Allow me to try to catch
up and comment on the topics brought up...
States:
==========================================================================
The listed states in the first post were simply my initial take on states.
They acted as a place holder in the design for future parsing states. As
for whether tag state is required: My feeling is that it is safer and more
accurate checking a state variable instead of trying to make an inference
from a pointer being NULL/non-NULL. I also feel that keeping state during
the tag parsing is much more efficient. Parsing the tag is more than doing
5 byte comparisons. Consider the following pathological case:
"<", "!", "-", "-", "#" each in their own brigades.
Ryan suggested that I just squirrel away the buckets into a set aside
brigade in the ctx then restart the tag checking at the beginning each
time mod_include is called.
This means that I re-iterate through not just a couple of byte compares for
each set aside bucket, but also the code required to read from the buckets,
and track compared positions. This isn't a lot of overhead, but it is more
than just 5 byte compares, and is easily avoided.
By the time I am done there are likely to be a number of other states used
during the directive parsing. These additional states will never be visible
across invocations of mod_include because they are only entered once the
full tag has been found. These states could be stored locally, but I feel
keeping all of the state information in one place makes more sense.
In summary: The number of states will grow to include parsing states. Tag state
is useful for code readability (state == X vs. brgd_ptr != NULL) and for
efficiency. And for crying out loud, the state variables are just an int and
a few pointers.
Max Buffer Size:
===========================================================================
In 1.3 Apache allowed each token to be a max of HUGE_STRING_LEN (8192 bytes).
The code did not read the whole directive in, it read bytes from what it
viewed as a file stream. I would guess that most tags would be less than
1KB total length, with some going more.
My feeling is to have a default buffer of say 512 or 1024, then alloc a larger
one if required (see next comment section about copying). This would be a
VERY local buffer only existing during the life of the send_parsed_content
function. It could be allocated and freed safely within that function, or
allocated from the request pool and cleaned up automagically later. I like
the local alloc and free better personally.
Copying:
===========================================================================
This will probably send Ryan into convulsions ;), but after studying the code
and having conversations with a couple of people and now having received
unsolicited agreement from Greg, I feel that making a copy once is the only
reasonable way to go.
Granted, Ryan is correct that the bucket handling code is contained in a couple
of functions. The problem is that these functions get called frequently and that
these function do a copy anyway. And not just a copy but a pool alloc and copy
for the values. So I don't think there can be any debate about copying. It is
currently happening and there is no way to completely remove copying. It would
be impossible, for example, to execute the setting of a variable with a value
that spans buckets.
What I suggest is to make one copy. There is still debate about whether to copy
as you go or copy once you have the whole thing. My feeling is that copying once
you have the whole thing allows you to determine how much space is required so
you can either use the local buffer or allocate a bigger one. This is an important
point since we really have no idea how big the thing can get, and we certainly
have no idea how big it is until we find the end.
I also advocate copying only the directive content (not the the start and end
delimiters). This provides a minor code simplification. The old code used the
end delimiter to mark the end of the stream for parsing purposes. Since we
already know where the end of the tag is, there is no sense complicating the
parsing code looking for the ending sequence again.
I also advocate not ever copying any part of the directive again. The tolower'ing
can be done in place. The values can be referenced in place. Every token has
a clear delimiter (white space, "=", "\0", etc.). These delimiters can be converted to
"\0" and pointers set to reference the bytes in place. During handle_set, for example,
the value gets apr_pstrdup'ed during the apr_table_setn call anyway.
So in summary, once the full tag has been obtained (and the directive bytes counted)
a buffer may be allocated and the directive bytes copied from the buckets into the
buffer. The parser will return pointers into this buffer after having marked the
end of the token with a NULL (tolower'ing as required). If the value must exist
outside of this buffer (i.e. for a set) then the value can be dup'ed as required.
One optimization would be to check if the whole directive is contained in one bucket
and just use that buffer instead of copying at all.
Grammar:
==============================================================================
I am working on a complete documented grammar for this. I will post it when it
is mostly complete. This post is already long enough so I will spare you all for now.
--
Paul J. Reder
-----------------------------------------------------------
"The strength of the Constitution lies entirely in the determination of each
citizen to defend it. Only if every single citizen feels duty bound to do
his share in this defense are the constitutional rights secure."
-- Albert Einstein
Re: Mod_include design
Posted by Greg Stein <gs...@lyra.org>.
On Thu, Nov 02, 2000 at 03:46:17PM -0500, Bill Stoddard wrote:
> > > But: it definitely depends on how bounded the size of a directive can be.
> I
> > > mean, can a directive be 10k long? If it is bounded, say, to MAX_PATH +
> 200,
> > > then we just put that buffer into the ctx and run with it.
> >
> > I don't see anything in 1.3 indicating that it is *theoretically*
> > bounded to a relatively small number... For example, consider the cmd
> > attribute on exec. (How long can a command-line be? way long...)
> >
> > *Practically* a human isn't going to deal with long (>2048-byte)
> > directives (though machine-generated directives have no such distaste).
> >
> > Overall I think collecting directive bytes into a buffer as we parse is
> > the way to go...
>
> The uri in "include virtual=uri" constructed dynamically (for example via a
> CGI) could be a quite large. I see no reason we shouldn't impose (and
> enforce) a reasonably large upper limit on tag length.
Well, it isn't hard to allocate a directive buffer of, say, 500 bytes. If
the user gives us a pathological case, then we simply grow the buffer. No
big deal. 99% of the time, we follow the fast-path with the 500 byte buffer
for the directive (tag+args+whatever)
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
Re: Mod_include design
Posted by Bill Stoddard <st...@raleigh.ibm.com>.
> > But: it definitely depends on how bounded the size of a directive can be.
I
> > mean, can a directive be 10k long? If it is bounded, say, to MAX_PATH +
200,
> > then we just put that buffer into the ctx and run with it.
>
> I don't see anything in 1.3 indicating that it is *theoretically*
> bounded to a relatively small number... For example, consider the cmd
> attribute on exec. (How long can a command-line be? way long...)
>
> *Practically* a human isn't going to deal with long (>2048-byte)
> directives (though machine-generated directives have no such distaste).
>
> Overall I think collecting directive bytes into a buffer as we parse is
> the way to go...
The uri in "include virtual=uri" constructed dynamically (for example via a
CGI) could be a quite large. I see no reason we shouldn't impose (and
enforce) a reasonably large upper limit on tag length.
Bill
Re: Mod_include design
Posted by Jeff Trawick <tr...@bellsouth.net>.
Greg Stein <gs...@lyra.org> writes:
> It will be *incredibly* easier to parse a directive if we can turn it into a
> contiguous string. Consider that we are going to have to do some level of
> copying to deal with the tag [for a strcmp], and then copy each argument
> into a new buffer, etc. The nature of this stuff is simply that we will
> eventually copy an entire directive anyhow, so let's just do it up front and
> simplify the parsing step.
yep
> If our goal is to rebuild mod_include into a *clean* and *maintainable*
> module, then this will be quite handy. The parsing step will be clear and
> quite servicable.
yep
> But: it definitely depends on how bounded the size of a directive can be. I
> mean, can a directive be 10k long? If it is bounded, say, to MAX_PATH + 200,
> then we just put that buffer into the ctx and run with it.
I don't see anything in 1.3 indicating that it is *theoretically*
bounded to a relatively small number... For example, consider the cmd
attribute on exec. (How long can a command-line be? way long...)
*Practically* a human isn't going to deal with long (>2048-byte)
directives (though machine-generated directives have no such distaste).
Overall I think collecting directive bytes into a buffer as we parse is
the way to go...
--
Jeff Trawick | trawick@ibm.net | PGP public key at web site:
http://www.geocities.com/SiliconValley/Park/9289/
Born in Roswell... married an alien...
Re: Mod_include design
Posted by Bill Stoddard <st...@raleigh.ibm.com>.
> On Thu, Nov 02, 2000 at 12:44:15PM -0800, rbb@covalent.net wrote:
> >...
> > Greg's comment that we might as well copy as we find the tag, I don't
> > agree with either. Picture a brigade that looks like:
> >
> > "<" -> "!" -> "-" -> "foobar"
> >
> > This is an invalid tag. If we copy as we find things, then we will copy
> > things into the buffer that isn't really a tag, and if we use the presence
> > of data in the buffer to siginify a tag, then we have a problem.
> >
> > If we copy the tag once we have found the full tag, then we can actually
> > allocate a buffer of the correct size for the tag that we have.
>
> You are going to do one of two things as you look for the tag:
>
> 1) set aside a brigade
> 2) copy into a buffer
>
> Given that (1) might do a copy, and that you will eventually do (2), then
> you may as well do it as you go.
>
> And, oh, gee, heavens-to-betsy, we find that the tag is invalid. Well, gosh
> darnit. We went and copied four bytes into a buffer and now we need to send
> that all down to the next filter.
>
> Yah, right. Like we need to be worried about those four bytes.
>
>
> Copy the darn thing until you find your tag. It keeps it clean and simple,
> and there is next to zero performance degradation. I don't understand the
> rationale for a bunch of complexity to avoid copying four bytes
Yes, I agree with Greg here. If you see what you think is a tag, assume it IS
a tag and copy it. If you later discover it is not really a tag, then send it
out on the wire. The performance impact is minimal and it is certainly not
worth adding even more complexity to the code to handle this case more
efficiently.
Bill
Bill
Re: Mod_include design
Posted by Greg Stein <gs...@lyra.org>.
On Thu, Nov 02, 2000 at 12:44:15PM -0800, rbb@covalent.net wrote:
>...
> Greg's comment that we might as well copy as we find the tag, I don't
> agree with either. Picture a brigade that looks like:
>
> "<" -> "!" -> "-" -> "foobar"
>
> This is an invalid tag. If we copy as we find things, then we will copy
> things into the buffer that isn't really a tag, and if we use the presence
> of data in the buffer to siginify a tag, then we have a problem.
>
> If we copy the tag once we have found the full tag, then we can actually
> allocate a buffer of the correct size for the tag that we have.
You are going to do one of two things as you look for the tag:
1) set aside a brigade
2) copy into a buffer
Given that (1) might do a copy, and that you will eventually do (2), then
you may as well do it as you go.
And, oh, gee, heavens-to-betsy, we find that the tag is invalid. Well, gosh
darnit. We went and copied four bytes into a buffer and now we need to send
that all down to the next filter.
Yah, right. Like we need to be worried about those four bytes.
Copy the darn thing until you find your tag. It keeps it clean and simple,
and there is next to zero performance degradation. I don't understand the
rationale for a bunch of complexity to avoid copying four bytes.
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
Re: Mod_include design
Posted by rb...@covalent.net.
On 2 Nov 2000, Jeff Trawick wrote:
> rbb@covalent.net writes:
>
> > > But: it definitely depends on how bounded the size of a directive can be. I
> > > mean, can a directive be 10k long? If it is bounded, say, to MAX_PATH + 200,
> > > then we just put that buffer into the ctx and run with it.
> >
> > I wouldn't personally put it into the ctx, because this will all be done
> > in a single call to the filter,
>
> but we aren't guaranteed that the entire tag is in the same
> brigade... isn't your reasoning for not putting it in the ctx based
> on a tag not crossing brigade boundaries?
Please read my previous messages again. I do garauntee that by the time
we are parsing the actual tag, it is in a single brigade. What I am
saying, is that we absolutely can not actually process the SSI tag until
we have all of it, so if we already have the full tag, then we don't need
the ctx field.
Greg's comment that we might as well copy as we find the tag, I don't
agree with either. Picture a brigade that looks like:
"<" -> "!" -> "-" -> "foobar"
This is an invalid tag. If we copy as we find things, then we will copy
things into the buffer that isn't really a tag, and if we use the presence
of data in the buffer to siginify a tag, then we have a problem.
If we copy the tag once we have found the full tag, then we can actually
allocate a buffer of the correct size for the tag that we have.
Ryan
_______________________________________________________________________________
Ryan Bloom rbb@apache.org
406 29th St.
San Francisco, CA 94131
-------------------------------------------------------------------------------
Re: Mod_include design
Posted by Jeff Trawick <tr...@bellsouth.net>.
rbb@covalent.net writes:
> > But: it definitely depends on how bounded the size of a directive can be. I
> > mean, can a directive be 10k long? If it is bounded, say, to MAX_PATH + 200,
> > then we just put that buffer into the ctx and run with it.
>
> I wouldn't personally put it into the ctx, because this will all be done
> in a single call to the filter,
but we aren't guaranteed that the entire tag is in the same
brigade... isn't your reasoning for not putting it in the ctx based
on a tag not crossing brigade boundaries?
--
Jeff Trawick | trawick@ibm.net | PGP public key at web site:
http://www.geocities.com/SiliconValley/Park/9289/
Born in Roswell... married an alien...
Re: Mod_include design
Posted by rb...@covalent.net.
> But: it definitely depends on how bounded the size of a directive can be. I
> mean, can a directive be 10k long? If it is bounded, say, to MAX_PATH + 200,
> then we just put that buffer into the ctx and run with it.
I wouldn't personally put it into the ctx, because this will all be done
in a single call to the filter, but yes if the directive length is
bounded, we could copy. Unfortunately, I don't think the length is
bounded, so I think we need to be able to deal with partial tags in a
bucket.
Ryan
_______________________________________________________________________________
Ryan Bloom rbb@apache.org
406 29th St.
San Francisco, CA 94131
-------------------------------------------------------------------------------
Re: Mod_include design
Posted by Greg Stein <gs...@lyra.org>.
On Thu, Nov 02, 2000 at 11:20:59AM -0800, rbb@covalent.net wrote:
> > Ryan, a state machine is how parsers like this work, in our "here is some
> > more text" model. It is required, but you can deny it all you like :-)
>
> Greg, the problem is where the state machine goes. I agree that there
> will be _A_ state machine in mod_include.
That was certainly /not/ clear :-)
> I disagree that it should be
> the state machine that Paul initially outlined. The state machine that he
> outlined was to determine how to split a tag out of the brigade. This is
> unnecessary. By just splitting the brigade at any subset of <!-- and
> -->, we can find the tag, and at that point we go into the state machine
> to actually parse the tag.
Sure.
>...
> > [ note that "buffer" could be a set-aside brigade; if you don't memcpy a
> > directive out of a brigade into a buffer, then the parsing becomes much
> > more difficult, and more states would be desirable to control and drive
> > the parsing ]
>
> I disagree that the copy is necessary, because the code is completely
> localized to one or two functions, but that's fine.
It will be *incredibly* easier to parse a directive if we can turn it into a
contiguous string. Consider that we are going to have to do some level of
copying to deal with the tag [for a strcmp], and then copy each argument
into a new buffer, etc. The nature of this stuff is simply that we will
eventually copy an entire directive anyhow, so let's just do it up front and
simplify the parsing step.
If our goal is to rebuild mod_include into a *clean* and *maintainable*
module, then this will be quite handy. The parsing step will be clear and
quite servicable.
But: it definitely depends on how bounded the size of a directive can be. I
mean, can a directive be 10k long? If it is bounded, say, to MAX_PATH + 200,
then we just put that buffer into the ctx and run with it.
Performance-wise: copying 80 bytes of directive text is meaningless (despite
the fact that we'd end up copying the tag and args anyways).
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
Re: Mod_include design
Posted by Bill Stoddard <st...@raleigh.ibm.com>.
The changes I had to make to get mod_cgissi.c working were really quite
minimal, the biggest being handling a tag spanning across a buffer. The main
work was to maintain state (2 states, in tag and not in tag), and some futzing
with GET_CHAR to work with a buffer rather than a file and indices into that
buffer. You could probably do something very similar with buckets rather than
buffers. In fact, you could probably extend my work to use buckets, not that
this is the best solution...
Bill
----- Original Message -----
From: <rb...@covalent.net>
To: <ne...@apache.org>
Sent: Thursday, November 02, 2000 2:20 PM
Subject: Re: Mod_include design
>
> > Ryan, a state machine is how parsers like this work, in our "here is some
> > more text" model. It is required, but you can deny it all you like :-)
>
> Greg, the problem is where the state machine goes. I agree that there
> will be _A_ state machine in mod_include. I disagree that it should be
> the state machine that Paul initially outlined. The state machine that he
> outlined was to determine how to split a tag out of the brigade. This is
> unnecessary. By just splitting the brigade at any subset of <!-- and
> -->, we can find the tag, and at that point we go into the state machine
> to actually parse the tag.
>
> > 1) not parsing a directive [pass all text up to a directive marker]
> > 2) parsing a directive [accumulate until we have a complete directive]
> >
> > These two states will exist, but it is entirely reasonable/possible that
it
> > will not be concretely exposed as a two-state machine. The state could
> > simply be "if anything is in the directive buffer, then we are in state 2;
> > if the buffer is empty, then we are in state 1".
>
> The state machine I am referring to, is the state that tries to find a
> tag. It is unnecessary to have a full-blown state machine that goes
> across filter invocations, because we can't deal with the tag until we
> have a full tag anyway, so saving the full state in the ctx pointer isn't
> required.
>
> > [ note that "buffer" could be a set-aside brigade; if you don't memcpy a
> > directive out of a brigade into a buffer, then the parsing becomes much
> > more difficult, and more states would be desirable to control and drive
> > the parsing ]
>
> I disagree that the copy is necessary, because the code is completely
> localized to one or two functions, but that's fine.
>
> Ryan
>
______________________________________________________________________________
_
> Ryan Bloom rbb@apache.org
> 406 29th St.
> San Francisco, CA 94131
> ----------------------------------------------------------------------------
---
>
Re: Mod_include design
Posted by rb...@covalent.net.
> Ryan, a state machine is how parsers like this work, in our "here is some
> more text" model. It is required, but you can deny it all you like :-)
Greg, the problem is where the state machine goes. I agree that there
will be _A_ state machine in mod_include. I disagree that it should be
the state machine that Paul initially outlined. The state machine that he
outlined was to determine how to split a tag out of the brigade. This is
unnecessary. By just splitting the brigade at any subset of <!-- and
-->, we can find the tag, and at that point we go into the state machine
to actually parse the tag.
> 1) not parsing a directive [pass all text up to a directive marker]
> 2) parsing a directive [accumulate until we have a complete directive]
>
> These two states will exist, but it is entirely reasonable/possible that it
> will not be concretely exposed as a two-state machine. The state could
> simply be "if anything is in the directive buffer, then we are in state 2;
> if the buffer is empty, then we are in state 1".
The state machine I am referring to, is the state that tries to find a
tag. It is unnecessary to have a full-blown state machine that goes
across filter invocations, because we can't deal with the tag until we
have a full tag anyway, so saving the full state in the ctx pointer isn't
required.
> [ note that "buffer" could be a set-aside brigade; if you don't memcpy a
> directive out of a brigade into a buffer, then the parsing becomes much
> more difficult, and more states would be desirable to control and drive
> the parsing ]
I disagree that the copy is necessary, because the code is completely
localized to one or two functions, but that's fine.
Ryan
_______________________________________________________________________________
Ryan Bloom rbb@apache.org
406 29th St.
San Francisco, CA 94131
-------------------------------------------------------------------------------
Re: Mod_include design
Posted by Greg Stein <gs...@lyra.org>.
On Thu, Nov 02, 2000 at 10:48:04AM -0800, rbb@covalent.net wrote:
> I wrote:
> > Paul -- yes, a clean parser is much more desirable. From your initial note,
> > I think you are definitely on the right track: a state machine to record
> > where you are in the parsing algorithm (and lexing if you separate that
> > out),
>...
>
> You can smack me all you want, but a state machine is still
> wrong. :-)
>...
Ryan, a state machine is how parsers like this work, in our "here is some
more text" model. It is required, but you can deny it all you like :-)
The exact form of that state machine is going to depend upon the grammar,
and on the model that Paul chooses for representing/parsing the grammar. At
a miminum you have two states:
1) not parsing a directive [pass all text up to a directive marker]
2) parsing a directive [accumulate until we have a complete directive]
These two states will exist, but it is entirely reasonable/possible that it
will not be concretely exposed as a two-state machine. The state could
simply be "if anything is in the directive buffer, then we are in state 2;
if the buffer is empty, then we are in state 1".
[ note that "buffer" could be a set-aside brigade; if you don't memcpy a
directive out of a brigade into a buffer, then the parsing becomes much
more difficult, and more states would be desirable to control and drive
the parsing ]
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
Re: Mod_include design
Posted by rb...@covalent.net.
> Paul -- yes, a clean parser is much more desirable. From your initial note,
> I think you are definitely on the right track: a state machine to record
> where you are in the parsing algorithm (and lexing if you separate that
> out), and storing context into the filter context (at one point, Ryan said
> something about a "static variable" -- I'll smack him for that next time I
> see him (he broke headers because he held context that way); use the context
> field like you intended).
You can smack me all you want, but a state machine is still
wrong. :-) If I said static variable, it was a mistake. What I meant
was a local variable. I didn't have great connectivity in London after
the conference, so I didn't always re-read before I sent the messages.
Ryan
_______________________________________________________________________________
Ryan Bloom rbb@apache.org
406 29th St.
San Francisco, CA 94131
-------------------------------------------------------------------------------
Re: Mod_include design
Posted by Greg Stein <gs...@lyra.org>.
On Fri, Oct 27, 2000 at 12:10:11PM -0700, rbb@covalent.net wrote:
> Paul Reder wrote:
> > > Plus, this really should be implemented as a real parser, not the current
> > > hack we have.
> >
> > I'm assuming you aren't looking for a full YACC/LEXX implemented parser for
> > this simple setup, just something cleaner and more formal than the kludged
> > string matcher that is currently there.
>
> Yes.
Paul -- yes, a clean parser is much more desirable. From your initial note,
I think you are definitely on the right track: a state machine to record
where you are in the parsing algorithm (and lexing if you separate that
out), and storing context into the filter context (at one point, Ryan said
something about a "static variable" -- I'll smack him for that next time I
see him (he broke headers because he held context that way); use the context
field like you intended).
I believe that you can probably update mod_include in several waves. In
fact, I would highly recommend this, so that the individual changes can be
reviewed. This also shows people progress, and keeps us from thinking "damn.
mod_include isn't going anywhere and needs to be fixed now". (I was berating
Ryan at the conference for breaking mod_include, then not fixing it; he
pointed out you were working on it, but that was news since I hadn't seen
anything (yet)).
What would be slick, and would help out your parsing work is to document the
grammar and put it into comments within mod_include. Once a rigorous grammar
is present, then it will be easier for us reviewers to check the work
against that grammar.
It seems that the discussion also mentioned handling of the tag and how it
might be split across buckets. The tag isn't going to be that long... memcpy
the darn thing into a holding buffer so you can do a strcmp(). I don't know
how long an individual directive may be, but it might be advantageous to
see if a maximum exists and copy directives into a holding buffer. NOTE:
this doesn't conflict with the "no copy" desires of buckets. The bucket of a
mod_include file is raw text rather than directives; that raw text won't get
copied (since you'd only copy to the buffer when a directive is seen). Using
a buffer for the tag/directives will simplify the context structure that you
posted: you'd only need a buffer for the directive that you're accumulating.
Any brigade contents from before the directive will have been passed. Any
brigade contents after a directive simply hasn't been parsed (yet) by the
mod_include filter and is still in a param/local variable on the execution
stack (cuz you won't return from the filter until you've completed parsing
through it; the only state for a return is "in a directive [and the
directive buffer is being filled]" or "outside a directive [and I'm not
holding anything in the directive buffer or a set-aside brigade]").
[ quick question: what *is* the max length? the grammar will help with that ]
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
Re: Mod_include design
Posted by rb...@covalent.net.
> First off, when I started working on this it wasn't yet hacked into mod_include so
> we came to basically the same conclusion concurrently.
No, it was always this design, it's just that it wasn't fully
implemented. It took a total of five minutes to add the set-aside
logic. It isn't perfect yet, but it does work 99% of the time.
> Second, I don't know where
> you are talking about memcpy's being done.
The comments in your initial message about copying the tag into a single
string.
> > But there is no state to save. I'll explain. If we have a brigade that
> > resolves to:
> >
> > foobar <!-
> >
> > then we want to split at < so that we have two brigades:
> >
> > "foobar " and "<!-"
> >
> > On the next call to the includes_filter, we just concat the two brigades,
>
> Where was the first brigade squirreled away until the second invocation of mod_include?
> Are you going to start checking for the STARTING_SEQUENCE from the beginning again,
> or are you going to pick up where you left off? If you will pick up where you left
> off (as my current code does) how do you know where to resume?
We should just check from the beginning. We are talking about a few
characters. It isn't worth it to avoid the four or five character
compares.
> Thank you for the specific example. This makes sense. I will work to rewrite
> the parser and processor as an integral part of the brigade processing. I can
> see the cases where just inserting on the fly would be appropriate. I would
> still assume that for cgi directives the leading buckets would be sent on
> since the processing could take a while. The cgi output would then be sent
> along as its own brigade later. Reasonable?
No, well yes, but the way this needs to be done, is that we need to pass
three brigades to all of the handle functions. The first section, the
tag, and the end. The handle_function then figures out what to send and
what to concat.
> > Plus, this really should be implemented as a real parser, not the current
> > hack we have.
>
> I'm assuming you aren't looking for a full YACC/LEXX implemented parser for
> this simple setup, just something cleaner and more formal than the kludged
> string matcher that is currently there.
Yes.
Ryan
_______________________________________________________________________________
Ryan Bloom rbb@apache.org
406 29th St.
San Francisco, CA 94131
-------------------------------------------------------------------------------
Re: Mod_include design
Posted by "Paul J. Reder" <re...@raleigh.ibm.com>.
rbb@covalent.net wrote:
> > As far as I can tell this is just a restatement of what I said. A tag can span
> > brigades. The pertinent bytes from the first brigade need to be split and set
> > aside so that they can be concat'ed to the following brigade so that the matching
> > and processing can continue. If I am incorrect please help me understand.
>
> You are correct, but that is already working supposedly, and there should
> be no reason to do any memcpy's to make this work completely. The problem
> is that your design is an exact re-statement of the current design.
>
First off, when I started working on this it wasn't yet hacked into mod_include so
we came to basically the same conclusion concurrently. Second, I don't know where
you are talking about memcpy's being done.
> But there is no state to save. I'll explain. If we have a brigade that
> resolves to:
>
> foobar <!-
>
> then we want to split at < so that we have two brigades:
>
> "foobar " and "<!-"
>
> On the next call to the includes_filter, we just concat the two brigades,
Where was the first brigade squirreled away until the second invocation of mod_include?
Are you going to start checking for the STARTING_SEQUENCE from the beginning again,
or are you going to pick up where you left off? If you will pick up where you left
off (as my current code does) how do you know where to resume?
> and we will have either:
>
> "<!-" "- garbage again"
>
> or
>
> "<!-" "garbage again"
>
> Notice, concat doesn't have anything to do with memcpy. Regardless, it is
> four compares to check the start tag and four for the ending tag. Since
> we need to do the split and keep the data around regardless, it doesn't
> make any sense to also save a state in that structure.
>
Again with the memcpy's. The concat that I spoke of was to concat two brigades.
If you are going to parse through a collection of buckets (or what eventually
gets concat'ed from multiple brigades into one brigade of buckets) why not tag
the interesting parts as you go? For instance, tag the starting point of the
SSI directive and compute its length when you run through the first time. This
saves having to parse through a second time trying to skip the tag to get to
the directive. And before you say "It is just 4 bytes.", they may be spread over
4 buckets. If you already did the parsing work once, why repeat? Store the pointers
as state info that is maintained from one invocation to the next. The state is
just a small set of pointers and indexes, there is no copying until the directive
is copied into a contiguous buffer (and even this is not strictly required).
> The problem is in taking this peice-meal. Fixing bucket handling without
> fixing the tag handling is not going to work. The bucket handling is
> intimatly tied to the tag handling. For example, if the tag is a set tag,
> it doesn't make any sense to send the data before we try to parse the tag,
> because the tag won't generate any data. I would like the handle_foo
> functions to return a bucket brigade that will be inserted into current
> brigade.
Thank you for the specific example. This makes sense. I will work to rewrite
the parser and processor as an integral part of the brigade processing. I can
see the cases where just inserting on the fly would be appropriate. I would
still assume that for cgi directives the leading buckets would be sent on
since the processing could take a while. The cgi output would then be sent
along as its own brigade later. Reasonable?
> That's fine. I was hacking in changes to get mod_include to work
> again. I would still like to see somebody else re-write mod_include,
> because I really just don't want to do it. However, if we are going to
> re-write it, we should be ripping out the guts and re-writing it, not
> conitnuing the hack that is currently in place.
Gut-ripping has commenced.
> Plus, this really should be implemented as a real parser, not the current
> hack we have.
I'm assuming you aren't looking for a full YACC/LEXX implemented parser for
this simple setup, just something cleaner and more formal than the kludged
string matcher that is currently there.
--
Paul J. Reder
-----------------------------------------------------------
"The strength of the Constitution lies entirely in the determination of each
citizen to defend it. Only if every single citizen feels duty bound to do
his share in this defense are the constitutional rights secure."
-- Albert Einstein
Re: Mod_include design
Posted by rb...@covalent.net.
> > No, the goal for mod_include is to re-write it to make it work much better
> > than it did in 1.3. Mod_include is a mess, and that includes all of the
> > tag handling. We don't need to worry about multiple brigades, because
> > simply setting the tags aside and concat'ing the two brigade together will
> > suffice for a tag that spans brigades. All we need is something that
> > allows a tag to span buckets, and the logic to set-aside the partial
> > brigades.
>
> As far as I can tell this is just a restatement of what I said. A tag can span
> brigades. The pertinent bytes from the first brigade need to be split and set
> aside so that they can be concat'ed to the following brigade so that the matching
> and processing can continue. If I am incorrect please help me understand.
You are correct, but that is already working supposedly, and there should
be no reason to do any memcpy's to make this work completely. The problem
is that your design is an exact re-statement of the current design.
> > What are you storing in the state machine? If you are storing the
> > state of the starting or ending sequence, can't this be done without
> > storing the state in the ctx pointer. I would rather see that work as a
> > static variable, much in the way it currently works. The only thing that
> > would need to be added, is the logic to split a bucket at the beginning of
> > the tag, even if the full tag isn't in this bucket.
>
> It is my understanding that mod_include is invoked fresh for each brigade.
> It is also my understanding that the appropriate place to store away persistent
> information across invocations (stuff that would ordinarily be static or
> global) is in the ctx. If the ctx is not for this purpose then what purpose
> does it serve?
But there is no state to save. I'll explain. If we have a brigade that
resolves to:
foobar <!-
then we want to split at < so that we have two brigades:
"foobar " and "<!-"
On the next call to the includes_filter, we just concat the two brigades,
and we will have either:
"<!-" "- garbage again"
or
"<!-" "garbage again"
Notice, concat doesn't have anything to do with memcpy. Regardless, it is
four compares to check the start tag and four for the ending tag. Since
we need to do the split and keep the data around regardless, it doesn't
make any sense to also save a state in that structure.
> > > >From here on, processing of the SSI tag proceeds as before.
> >
> > I really dislike this statement. The whole point of this was to try to
> > clean all of this up, not to hack something new into place.
>
> As I stated at the top of my note, my perspective was just my current
> understanding and I was looking for feedback. I am perfectly happy to work
> on rewriting the tag processing as well. I think I would prefer to handle that
> as a second phase of optimization after the bucketized code is working and
> committed. That way, everyone has a working include filter while the rest of
> the work is happening.
The problem is in taking this peice-meal. Fixing bucket handling without
fixing the tag handling is not going to work. The bucket handling is
intimatly tied to the tag handling. For example, if the tag is a set tag,
it doesn't make any sense to send the data before we try to parse the tag,
because the tag won't generate any data. I would like the handle_foo
functions to return a bucket brigade that will be inserted into current
brigade.
> > I would like to see mod_include re-written, so that the handle_foo
> > functions actually return a brigade and that brigade is inserted into the
> > original brigade in place of the original tag.
>
> I guess my high level design was too high. My rewrite, as it stands now, pulls the
> buckets related to the tag out of their brigades (passing along the brigades
> that precede the tag, splitting the final bucket at the tag) then creates a new
> brigade containing the content generated by the tag processing. The new brigade
> is not inserted into the original brigade since that brigade has already been
> passed on. The new brigade is passed along as a separate brigade.
I understand your design. It is the exact same as the current design that
I hacked into the old mod_include. The is the design that I was talking
about getting rid of when I talked about re-writing mod_include.
> > I was asked to make mod_include work this week, because we want to try to
> > get 2.0 running on locus. That requires that we be able to at least serve
> > SSI pages. This doesn't affect you negatively at all, because all of
> > these hacks that I am adding should be taken care of by your own
> > code. Just copy mod_include off to the side before you do an update, then
> > copy it back afterwards.
>
> Sorry, I was just feeling a little tense. I'm trying to work as fast as I can, but
> feel like there isn't room for a new guy to learn the ropes. I realize that there
> is a lot of desire to get this to come together soon. But I also feel that if you
> want help from more than just the current core of coders that new guys need time to
> learn all of the changes that have occurred. I know 1.3 pretty well, but haven't had
> time to keep up with all of the 2.0 changes. I'm using mod_include to learn so that
> I can contribute more in the future. It will take me longer than you to get this together.
That's fine. I was hacking in changes to get mod_include to work
again. I would still like to see somebody else re-write mod_include,
because I really just don't want to do it. However, if we are going to
re-write it, we should be ripping out the guts and re-writing it, not
conitnuing the hack that is currently in place.
Plus, this really should be implemented as a real parser, not the current
hack we have.
Ryan
_______________________________________________________________________________
Ryan Bloom rbb@apache.org
406 29th St.
San Francisco, CA 94131
-------------------------------------------------------------------------------
Re: Mod_include design
Posted by "Paul J. Reder" <re...@raleigh.ibm.com>.
Ryan,
I think we are pretty much on the same page. I agree that mod_include can be
cleaned up and optimized. I just hadn't picked that up in the passing messages
as being one of the immediate goals. Please see the rest of my embedded comments.
rbb@covalent.net wrote:
>
> > Basically, as I understand it, mod_include needs to be fixed to handle SSI
> > tags that can span multiple buckets or, in worst case, multiple brigades.
> > The rest of the SSI processing (once the tag is obtained) seems to be ok.
> > In order to do this I am converting mod_include to be a state machine with
> > the state stored in the attached data structure in the filter ctx.
>
> No, the goal for mod_include is to re-write it to make it work much better
> than it did in 1.3. Mod_include is a mess, and that includes all of the
> tag handling. We don't need to worry about multiple brigades, because
> simply setting the tags aside and concat'ing the two brigade together will
> suffice for a tag that spans brigades. All we need is something that
> allows a tag to span buckets, and the logic to set-aside the partial
> brigades.
As far as I can tell this is just a restatement of what I said. A tag can span
brigades. The pertinent bytes from the first brigade need to be split and set
aside so that they can be concat'ed to the following brigade so that the matching
and processing can continue. If I am incorrect please help me understand.
>
> > HIGH LEVEL DESIGN:
> >
> > Buckets are parsed until the STARTING_SEQUENCE (or at least the first byte(s))
> > are found. Once the STARTING_SEQUENCE is found, buckets are set aside into
> > the ssi_brigade in ctx until the ENDING_SEQUENCE is found. The bucket containing
> > the first byte of the STARTING_SEQUENCE is split at the first byte. All buckets
> > up to the new split bucket are passed on.
> >
> > If a partial STARTING_SEQUENCE is found at the end of a bucket, that bucket is split
> > and set aside. If the bytes in the next bucket do not continue to match the
> > STARTING_SEQUENCE the state machine is reset. The set aside buckets will be passed on.
>
> What are you storing in the state machine? If you are storing the
> state of the starting or ending sequence, can't this be done without
> storing the state in the ctx pointer. I would rather see that work as a
> static variable, much in the way it currently works. The only thing that
> would need to be added, is the logic to split a bucket at the beginning of
> the tag, even if the full tag isn't in this bucket.
It is my understanding that mod_include is invoked fresh for each brigade.
It is also my understanding that the appropriate place to store away persistent
information across invocations (stuff that would ordinarily be static or
global) is in the ctx. If the ctx is not for this purpose then what purpose
does it serve?
The information stored in the state machine was described in the comments for
the data structure that is being used (attached to the end of my post). Is there
something related to the comments about which you have a question?
>
> > >From here on, processing of the SSI tag proceeds as before.
>
> I really dislike this statement. The whole point of this was to try to
> clean all of this up, not to hack something new into place.
As I stated at the top of my note, my perspective was just my current
understanding and I was looking for feedback. I am perfectly happy to work
on rewriting the tag processing as well. I think I would prefer to handle that
as a second phase of optimization after the bucketized code is working and
committed. That way, everyone has a working include filter while the rest of
the work is happening.
>
> I would like to see mod_include re-written, so that the handle_foo
> functions actually return a brigade and that brigade is inserted into the
> original brigade in place of the original tag.
I guess my high level design was too high. My rewrite, as it stands now, pulls the
buckets related to the tag out of their brigades (passing along the brigades
that precede the tag, splitting the final bucket at the tag) then creates a new
brigade containing the content generated by the tag processing. The new brigade
is not inserted into the original brigade since that brigade has already been
passed on. The new brigade is passed along as a separate brigade.
>
> > I'm sorry this has taken me so long, but I have been out of the 2.0 loop for
> > a while and have had a lot to learn with all of the brigade and filter
> > code. I have been picking up steam over the past couple of days and hope to
> > have something working in the next couple of days. It would be very helpful if
> > I were allowed to finish this without dribs and drabs of patches to get this
> > piece or that piece fixed in the current version, it just means I need to manually
> > merge the parts of these patches that still apply into the rewritten code to keep
> > them in synch.
>
> I was asked to make mod_include work this week, because we want to try to
> get 2.0 running on locus. That requires that we be able to at least serve
> SSI pages. This doesn't affect you negatively at all, because all of
> these hacks that I am adding should be taken care of by your own
> code. Just copy mod_include off to the side before you do an update, then
> copy it back afterwards.
Sorry, I was just feeling a little tense. I'm trying to work as fast as I can, but
feel like there isn't room for a new guy to learn the ropes. I realize that there
is a lot of desire to get this to come together soon. But I also feel that if you
want help from more than just the current core of coders that new guys need time to
learn all of the changes that have occurred. I know 1.3 pretty well, but haven't had
time to keep up with all of the 2.0 changes. I'm using mod_include to learn so that
I can contribute more in the future. It will take me longer than you to get this together.
--
Paul J. Reder
-----------------------------------------------------------
"The strength of the Constitution lies entirely in the determination of each
citizen to defend it. Only if every single citizen feels duty bound to do
his share in this defense are the constitutional rights secure."
-- Albert Einstein
Re: Mod_include design
Posted by rb...@covalent.net.
> Basically, as I understand it, mod_include needs to be fixed to handle SSI
> tags that can span multiple buckets or, in worst case, multiple brigades.
> The rest of the SSI processing (once the tag is obtained) seems to be ok.
> In order to do this I am converting mod_include to be a state machine with
> the state stored in the attached data structure in the filter ctx.
No, the goal for mod_include is to re-write it to make it work much better
than it did in 1.3. Mod_include is a mess, and that includes all of the
tag handling. We don't need to worry about multiple brigades, because
simply setting the tags aside and concat'ing the two brigade together will
suffice for a tag that spans brigades. All we need is something that
allows a tag to span buckets, and the logic to set-aside the partial
brigades.
> HIGH LEVEL DESIGN:
>
> Buckets are parsed until the STARTING_SEQUENCE (or at least the first byte(s))
> are found. Once the STARTING_SEQUENCE is found, buckets are set aside into
> the ssi_brigade in ctx until the ENDING_SEQUENCE is found. The bucket containing
> the first byte of the STARTING_SEQUENCE is split at the first byte. All buckets
> up to the new split bucket are passed on.
>
> If a partial STARTING_SEQUENCE is found at the end of a bucket, that bucket is split
> and set aside. If the bytes in the next bucket do not continue to match the
> STARTING_SEQUENCE the state machine is reset. The set aside buckets will be passed on.
What are you storing in the state machine? If you are storing the
state of the starting or ending sequence, can't this be done without
storing the state in the ctx pointer. I would rather see that work as a
static variable, much in the way it currently works. The only thing that
would need to be added, is the logic to split a bucket at the beginning of
the tag, even if the full tag isn't in this bucket.
> >From here on, processing of the SSI tag proceeds as before.
I really dislike this statement. The whole point of this was to try to
clean all of this up, not to hack something new into place.
I would like to see mod_include re-written, so that the handle_foo
functions actually return a brigade and that brigade is inserted into the
original brigade in place of the original tag.
> I'm sorry this has taken me so long, but I have been out of the 2.0 loop for
> a while and have had a lot to learn with all of the brigade and filter
> code. I have been picking up steam over the past couple of days and hope to
> have something working in the next couple of days. It would be very helpful if
> I were allowed to finish this without dribs and drabs of patches to get this
> piece or that piece fixed in the current version, it just means I need to manually
> merge the parts of these patches that still apply into the rewritten code to keep
> them in synch.
I was asked to make mod_include work this week, because we want to try to
get 2.0 running on locus. That requires that we be able to at least serve
SSI pages. This doesn't affect you negatively at all, because all of
these hacks that I am adding should be taken care of by your own
code. Just copy mod_include off to the side before you do an update, then
copy it back afterwards.
Ryan
_______________________________________________________________________________
Ryan Bloom rbb@apache.org
406 29th St.
San Francisco, CA 94131
-------------------------------------------------------------------------------