[Tinycc-devel] Fixes to bcheck and how it works correctly

[Kirill Smelkov]

On Sun, Dec 09, 2012 at 10:44:01PM +0100, grischka wrote:
> Kirill Smelkov wrote:
> >Also grischka writes:
> >>btest is not a feature that we can't recommend to use
> >>really (at least as long as tcc -btest tcc.c doesn't produce anything
> >>useful),
> >
> >FYI, as of mob a55ecf6d it now does, so please don't treat -b mode as
> >second class citizen anymore.
> 
> Ok.  I admit that I never tried to understand how it really works.

Knowledge shared near the end...


> I have questions though regarding your change to the tcc code with
> 
>      vtop = vstack - 1;
> 
> Basically this is not wrong as the code never tries to access this
> address.  The point of this "trick" obviously is that we can
> pre-increment vtop and still not waste the first entry.
> 
> Anyway, to get rid of this somehow non-obvious code you could have
> changed it to
> 
>      vtop = vstack;
> 
> But that is not what you do, instead you introduce some macro magic
> which looks interesting but does nothing different, i.e. it also
> wastes the first entry in vstack.  So what is the point with that?

The point here is that there are places in tccgen, which either
iterate through vstack, or compute its length, or check whether the
stack is empty, and it all looks like

    /* iterate */
    for (p=vstack; p<=vtop; p++) {
        ...

    /* see, whether vstack is not empty */
    if (vtop >= vstack) {
        ...

which looks convenient, but if we initialize

    vtop = vstack;

above should be changed to

    /* iterate */
    for (p=vstack+1; p<vtop; p++) {
        ...

    /* see, whether vstack is not empty */
    if (vtop > vstack) {
        ...


but then in e.g. vsetc(), not to waste first entry we'll have to increment
vtop after v-item assignment, and then loose the very handy convention
that *vtop actually refers to top item.

Or, if we leave vtop pre-increment in vset(), then we have to iterate
like this:

    /* iterate */
    for (p=vstack+1; p<=vtop; p++) {
        ...

which to me is easy to make mistake in.

Overall I liked original vstack and vtop assignment rules, only it had
to deal with initial vstack-1 somehow. And documentation about vstack
and vtop and everything else stays the same. I don't insist my way is
good 100% good though...


> However the more interesting question is, why at all is that a problem
> with the bounds-checker?  Should it not warn only when a pointer is
> dereferenced to an invalid address?  Because, if we need to "fix"
> correct code in tcc to work with -b, then what about equally correct
> code elsewhere that also would not cooperate well with -b but that
> we (you) cannot fix?

I've started with the same question, and the answer here is that for -b
you have to pay some price code-wise:

Let's imagine that bcheck checks pointers only on dereference. Then
let's consider following:

    int a[10], b[10];

If we have p=&b[0], then do p--, how do we know whether there is no
bounds error for p? p points to correct memory &a[9], but it is out of
bounds - it started from b and crossed the limit.

That's why in lib/bcheck pointers are checked not only on indir, but
also on add. And that's why we have to pay the price. Btw - maybe "not
ansi" comment was there for a reason...

> >Thanks,
> >Kirill
> 
> Thanks for shedding some lights into this dark corner of tcc code. ;)

Nevermind. Here is what I've learned about how lib/bcheck.c works:

Memory is treated as regions. Every region could be either

    - empty,
    - invalid, or
    - valid

empty region means nothing is known about memory (for heterogenous
non-bcheck & bcheck code to operate), invalid means access to region is
forbidden and valid means access to region is ok.

On program start malloc zone and pointers near ffffffff are marked as
invalid, and memory for static arays is marked as valid.

At runtime, in every function, locals are marked as valid memory by
generated function prologue, and unmarked in epilogue.

Also malloced memory is also registered as valid regions with the help
of malloc hooks.

On every pointer dereference, or add __bound_indir*() or __bound_add()
is called which check whether the pointer is ok.

To do so, 32-bit addresses are considered as follows:

    +-------------+-----------+--------+
    | t1_idx 13   | t2_idx 11 | rest 8 |
    +-------------+-----------+--------+

and then there is a 2 level pagetable:

      T1        T2

    +----+    +----------- - - - -+----+
    |t1=0| -> |t2=0|   1|         |2048|
    +----+    +----+----+- - - - -+----+
    |   1| -> |t2=0|   1|         |2048|
    +----+    +----+----+- - - - -+----+
    |    |    .
    .    .         .
    .    .              .
    .    .                   .
    |8192|                        .   
    +----+                             .

with lazy copy-on-write T2.

each T2 entry forms a linked list of

    typedef struct BoundEntry {
        unsigned long start;
        unsigned long size;
        struct BoundEntry *next;
        unsigned long is_invalid; /* true if pointers outside region are 
invalid */
    } BoundEntry;


and having addr, the code walks this list to find appropriate
(start, size) entry.


Found, it does the checks and voila.

NOTE: for size, two special values are used: 0x00000000 for invalid
regions and 0xffffffff for empty regions (choosen so that `addr-start <=
size` works as intened for all cases).




Thanks,
Kirill

(sorry, this mail was composed partly in a hurry)