Subject: RE: [rohc] WGLC comments to torture-tests and user-guide

From: "Surtees, Abigail" <[email-masked]>
Date: Tue, 23 Aug 2005 14:40:04 +0100

Hi Pekka,
> 
> >I think this would lead to quite a lot of duplication of information
> >within the document, so I'm inclined to say I don't think it's
> >necessary.  It would also need lots of checking to ensure 
> there aren't
> >contradictions between tests and appendix.
> 
> What I'd like to see in appendix A would be low-level reason (a'la
> RFC 4077 reason code), The point of providing reason codes in
> sigcomp-torture-tests is the amount of checking, should everyone
> running torture-tests do it, or should it be done only once.
> 

OK, a low level reason should be easy enough to add.  

> >> Also, it would be nice to clarify what is the area of memory the
> >> readonly() directive acts on in section 3.2.3
> 
> >Agreed.  How about:
> 
> >"The default assumption is that all memory can be changed during
> >execution of the UDVM.  That is, that unless stated 
> otherwise,  memory
> >is assumed to be readonly (0).  The area of memory covered 
> by a readonly
> >(1) directive is the area between that directive and either 
> a readonly
> >(0) directive or the end of the bytecode (whichever is the smaller
> >area)."
> 
> OK, but then you need to add readonly(1) to all example algorithms
> using !. What about:
> 
>    The default assumption is that all memory outside bytecode can be
>    changed during execution of the UDVM. That is, that unless stated
>    otherwise, memory from 0 to (destination - 1) is assumed to be
>    readonly (0), memory area from (destination) to the end of the
>    bytecode is readonly (1), and memory from the end of bytecode to
>    the end of udvm memory is is readonly(0). The area of memory
>    covered by a readonly directive is the area between that directive
>    and either an another readonly directive or the end of the
>    bytecode (whichever is the smaller area).
> 
This raises an interesting question.  There seem to be 3 possibilities
for default behaviour:

1) Assume all memory is readonly(0)
  + traps use of '!' without directives
  + simpler translator (there is no need for intelligence -- just work
with imposed
    constraints of directives)
  - cannot translate existing code without adding directives

2) Split the memory as above, 
  - this raise several questions that would have to be answered:
	- how do you define the start of bytecode? (is a 'pad' bytecode?
is 'byte' bytecode or does it begin when you find an actual VM
instruction..?)

	- how do you define the end of bytecode? (what about trailing
'0' parameters that don't need to be explicitly sent and trailing
'byte's that may/may not be over-written..?)

	- do you try and catch mutable regions in the middle of
bytecode?

	- what is the precedence and interaction between implicit
switches and explicit directives (if I set something to readonly(0)
explicitly prior to the start of bytecode, does it override the implicit
switch to readonly(1), or not..?)

3) Assume all memory is readonly(1) 
  + can translate existing code without adding directives
    (but the translated bytecode may not work :-S )
  - cannot trap use of '!', there will always be some
  - assumes that translator tries to make a faintly intelligent choice
of byte to use (this directive is then an 'optimisation' rather than a
'necessity')

Clearly 2) could be done by defining a set of rules but it seems
unnecessarily complex (a) to specify now; (b) to be sure that the rules
are sensible and thoroughly tested, partly because (c) it will be much
harder to implement such a set of implicit rules.  So I suggest that:

	- either 1) or 3) is used - the question is which?

	- torture tests using ! are changed to have explicit
decompression failure.  The torture tests are aiming to test the UDVM
not the translator, so having the smallest amount of ambiguity in
translation would be good.  The affected tests are Arithmetic,
MULTILOAD, CRC, State creation, State Access, Useful values, Input past
the end of message, Feedback mechanism, State memory management,
Multiple compartments, Bytecode state creation.

	- user guide - when the decision of which to use has been made,
the algorithms are updated with the readonly directive.  These
algorithms are showing use of mnemonic code (including directives) so
examples of the use of readonly would be good.

What do you think?

> >"The length of the resulting bytecode is dependent on the 
> parser used.
> >Bytecode can be correct and useable without being the 
> smallest possible
> >representation."
> 
> OK. Also replace [parser] "inserts the shortest bytecode capable
> of encoding" => "usually inserts the shortest bytecode capable of
> encoding".
> 
Being slightly pedantic - what does the parser/translator do in the
unusual case? ;-)

How about "inserts bytecode (usually the shortest) capable of
encoding..."?

> >> Random late improvement: unknown assembly directives should 
> >> be ignored.
> 
> >I'm not sure that unknown directives should necessarily be ignored -
> >there are some e.g. readonly that are a help to a translator/parser
but
> >others e.g. byte define specific behaviour for compilation.  
> I think the
> >important ones are covered by this draft.  If users want to make up
> >additional ones to help their particular compile they can, 
> but I don't
> >think they (or the fact that there could be others) need to 
> be in this
> >document.  What do you think?
> 
> I was thinking that a UDVM assembler should have a way to support
> non-standard directives.  So,  define
> 
>    directive /= unknown-directive
> 
>    unknown-directive = name ["(" expression *("," expression) ")"]
> 
> and the parser should ignore all <unknown-directive>. 
> 
> Or define
> 
>    directive /= private-directive
> 
>    private-directive = "__" name ["(" expression *("," ; 
> expression) ")"]
> 
> and the parser should ignore all <private-directive>. 
> 
OK, I'd go with unknown-directive as defined above.  The
parser/translator can indeed ignore the directive but the correctness of
the resulting bytecode (when it's run) will depend on what the directive
was intended to do and the sophistication of the parser/translator (was
the directive an optimisation or an order).

Best regards,

Abbie

> --Pekka

_______________________________________________
Rohc mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rohc

---

From: Pekka Pessi <[email-masked]>
Date: Wed, 24 Aug 2005 11:18:23 +0300

Hi Abigail,

"Surtees, Abigail" <[email-masked]> writes:
>[...] This raises an interesting question. There seem to be 3
>possibilities for default behaviour:

>is 'byte' bytecode or does it begin when you find an actual VM

I guess that must be the destination, ie., first non-zero byte in 
bytecode (at n * 64 + 128 byte boundary).

>'byte's that may/may not be over-written..?)

That is more trickier. In my code I've just assumed that the last
instruction or byte directive belongs to bytecode, so I can search
for ! destination until its end. IOW, before bytecode I have only
pad() or zero byte()s, after bytecode only pad()s. Currently, I
laso skip pad()s within bytecode.

>	- do you try and catch mutable regions in the middle of

This was the whole point of readonly()?

>switch to readonly(1), or not..?)

The implicit readonly(1) at the beginning of bytecode should
override prior readonly(0).

>harder to implement such a set of implicit rules.  

I think that all assemblers supporting ! already implement some
implicit rules regarding readonly, even if they do not support
readonly directive. Christian?

>So I suggest that:

>	- either 1) or 3) is used - the question is which?

I vote for 2) but 1 is OK, too.

>What do you think?

This is OK, too.

>Being slightly pedantic - what does the parser/translator do in the

It oscillates until the Turing tape is all worn out. (IOW, it
inserts the shortest bytecode, and in the next pass, notices that
the value to be encoded has changed, inserts the new and longer
bytecode, again in next pass notices that the value to be encoded
has changed again, inserts the original bytecode, ad infinitum).

>How about "inserts bytecode (usually the shortest) capable of

That sounds about right. My English fails me, unfortunately.

--Pekka

---

From: Cristian CONSTANTIN <[email-masked]>
Date: Wed, 24 Aug 2005 11:21:52 +0200

> 'byte's that may/may not be over-written..?)
cristian: you could could take as start the entry point (destination in sigcomp
parlance) an pass it as a parameter to the assembler, and you could consider
END-MESSAGE() as the end of it; I think all of the examples are in line
with this "model". however due to the design of the UDVM you could have
code after END-MESSAGE() and you could have data mixed with the code
itself; so this is only some heuristic...

> 	- do you try and catch mutable regions in the middle of

cristian: if your assembler performs some kind of control flow analysis you 
can distinguish btw. code and data in your bytecode: you can build a list of  
(extendend) basic blocks - this is your initial "code segment". 
you can discover then the initial "data holes" in your "code segment"; 
I think it is impossible (i.e. not Turing computable) though to detect
at assembly time (i.e. without actually running the UDVM bytecode) which 
one of the "data holes" or which block of your "code segment" in your 
bytecode is mutable (that is, which is going to change at run-time). 
you can do it at run-time by rebuilding the basic block list after 
executing any instruction that does a memory write which can affect the 
current memory configuration; but if the wrong address was used for a
"!" operator it would be too late wouldn't it?

> switch to readonly(1), or not..?)

cristian: the directives should always have priority.

> of byte to use (this directive is then an 'optimisation' rather than a

cristian: in fact in the general case, the translator _cannot_ make any 
intelligently enough choice; please see above.  

> What do you think?

cristian: I think the use of the readonly() directives it is the only
non-ambigous (as in clear) way of specifying which of your memory chunks
is ro and which is rw. on the other hand modifying existing UDVM code
which uses "!" would mean more work for the editors of the drafts...
so I don't know what to say.

bye now!
cristian
-- 
 _          | There are many people who use UNIX or Linux  
(_'_        | who IMHO do not understand UNIX.
  (_'rist   |              --David Korn  
GPG public key at wwwkeys.de.pgp.net
_______________________________________________
Rohc mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rohc

---

From: Mark West <[email-masked]>
Date: Wed, 24 Aug 2005 10:16:10 +0100 (BST)

Hi Pekka, all,

I think that we failed to completely follow through on the discussion of
this issue when it was originally raised.  It comes down, I believe, to a
choice:

i) specifying the legitimate targets for '!' should be done explicitly
   (see, e.g., Carsten's "strawman" proposal, in
    http://www1.ietf.org/mail-archive/web/rohc/current/msg03660.html)

ii) the assembler is assumed to make use of sensible heuristics for
    managing '!'; directives have been added to make life easier for
    people who think that self-modifying code is pretty neat idea ;-)
    (see, e.g. Carsten's suggested heuristic, in
     http://www1.ietf.org/mail-archive/web/rohc/current/msg03662.html
     corroborated by Adam)

So, on Abbie's list, option (1) corresponds pretty much directly with (i),
above -- you can't use '!' unless you have the appropriate directives.

Options (2) and (3) correspond with (ii), above -- you can use '!', but
either need good heuristics and/or appropriate directives.

The difference between options (2) and (3) is that (2) spells out *what*
the heuristics are and the interactions between these and the directives.

Example:

	ADD ($value, 1)
	JUMP (somewhere_else)
	readonly (0)
	byte (0x40)
	byte (0x41)
	:somewhere_else
	SUB ($value, 1)

When we go back into bytecode at ':somewhere_else', does this imply
'readonly(1)' or do we rely on explicit cues?  Is this different (and in
what way) from *not* having the directive and using the 'only code can be
a target for "!"' heuristic?  Option (2) has to nail these things down.

Option (3) says that we assume everything carries on the same way as
before, but there are now some additional directives.  You can use
whatever heuristics you like *but* you are absolutely *not* allowed to
make use of any bytes between a readonly(1)/readonly(0) pair as a target
for '!'.

Personally, I like (1) or (3). (1) is simple (you have to put
directives in; no need for smarts in the assembler).  (3) means that I can
continue to use the heuristics I've already coded up, but adds support for
the directives if someone ever throws self-modifying code in my direction.
(2) will lead, I suspect, to more wrangling over which heuristics to
specify, etc...

Given I've got a working assembler, I think I'd lean towards (3), but I'm
not too bothered [and I know Abbie & I disagree on this one :-)]

Cheers,

Mark.

---

From: Cristian CONSTANTIN <[email-masked]>
Date: Wed, 24 Aug 2005 11:56:34 +0200

> readonly directive. Christian?

cristian: yes, you are right. and as adam roach also has said in an
e-mail the heuristic "look for ! addresses among your translated instructions" 
works for all of UDVM code in the two drafts; these samples seem to be
clean and simple from this point of view. I didn't have problems
translating them without readonly() directives either... 

2) is trying to tell you what kind of heuristics your translator should
use; I guess this is too much for an rfc to specify. 

bye now!
cristian