Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #15314 > unrolled thread

Buffer access with bounds checking...

Back to article view | Back to comp.lang.forth

Contents

  Buffer access with bounds checking... Mark Wills <markrobertwills@yahoo.co.uk> - 2012-08-31 06:51 -0700
    Re: Buffer access with bounds checking... Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-08-31 11:04 -0500
    Re: Buffer access with bounds checking... Alex McDonald <blog@rivadpm.com> - 2012-08-31 09:20 -0700
      Re: Buffer access with bounds checking... Mark Wills <markrobertwills@yahoo.co.uk> - 2012-08-31 12:57 -0700
        Re: Buffer access with bounds checking... "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-08-31 18:46 -0400
          Re: Buffer access with bounds checking... Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-09-01 04:05 -0500
            Re: Buffer access with bounds checking... "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-01 13:45 -0400
              Re: Buffer access with bounds checking... Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-09-02 04:19 -0500
                Re: Buffer access with bounds checking... "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-09-02 16:15 -0400
                  Re: Buffer access with bounds checking... Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-09-04 12:02 -0500
    Re: Buffer access with bounds checking... Doug Hoffman <glidedog@gmail.com> - 2012-08-31 14:15 -0400
      Re: Buffer access with bounds checking... Mark Wills <markrobertwills@yahoo.co.uk> - 2012-08-31 12:56 -0700
      Re: Buffer access with bounds checking... Paul Rubin <no.email@nospam.invalid> - 2012-08-31 13:32 -0700
        Re: Buffer access with bounds checking... Doug Hoffman <glidedog@gmail.com> - 2012-08-31 17:45 -0400
          Re: Buffer access with bounds checking... Paul Rubin <no.email@nospam.invalid> - 2012-08-31 15:07 -0700
            Re: Buffer access with bounds checking... Mark Wills <forthfreak@gmail.com> - 2012-09-01 00:49 -0700
              Re: Buffer access with bounds checking... Paul Rubin <no.email@nospam.invalid> - 2012-09-01 14:06 -0700
                Re: Buffer access with bounds checking... Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-09-02 04:21 -0500
                Re: Buffer access with bounds checking... anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-09-02 10:27 +0000
            Re: Buffer access with bounds checking... Doug Hoffman <glidedog@gmail.com> - 2012-09-01 06:59 -0400
    Re: Buffer access with bounds checking... humptydumpty <ouatubi@gmail.com> - 2012-08-31 14:21 -0700
    Re: Buffer access with bounds checking... "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-08-31 18:48 -0400
    Re: Buffer access with bounds checking... Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-01 01:41 +0200
      Re: Buffer access with bounds checking... Bernd Paysan <bernd.paysan@gmx.de> - 2012-09-01 02:37 +0200
      Re: Buffer access with bounds checking... mhx@iae.nl (Marcel Hendrix) - 2012-09-01 11:11 +0200

Page 2 of 2 — ← Prev page 1 [2]

#15334

On Friday, August 31, 2012 1:51:59 PM UTC, Mark Wills wrote:
> While writing about memory buffer overruns in a different thread
> 
> earlier today, I was inspired to have a bash at writing some
> 
> code that would allow safe read/write access to memory buffers.
> 
> 
> 
> I came up with the code and wonder if it could be simplified or
> 
> improved any.
> 
> 
> 
> It's very simple. When a buffer is created, the first four cells
> 
> are reserved for the following:
> 
> * The pfa of the buffer (i'll explain in a minute)
> 
> * The size of the buffer in bytes
> 
> * The lowest legally accessible address
> 
> * The highest legally accessible address
> 
> 
> 
> It's possible to compute the last two items on the fly of
> 
> course, but I chose to do the math once and store the computed
> 
> result, rather than compute it on each buffer access, for
> 
> performance reasons.
> 
> 
> 
> The pfa of the buffer is stored so that accesses to the *same*
> 
> buffer can be detected, thus the buffer management variables
> 
> do not have to be re-computed.
> 
> 
> 
> I think the code below is portable (gave it a quick spin in
> 
> MINOS and it ran fine (disclaimer: my system doesn't have
> 
> CELLS+)
> 
> 
> 
> It struck me after writing it that if one used an offset to
> 
> reference a buffers' contents rather than an absolute address
> 
> then the code could be simplified somewhat.
> 
> 
> 
> -------------------------
> 
> 
> 
> variable _bufPfa
> 
> variable _bufSize
> 
> variable _lowBound
> 
> variable _topBound
> 
> 
> 
> : cells+ compile cells compile + ; immediate
> 
> 
> 
> : buffer ( int: size "name" --    children: -- address)
> 
>   create here ,         \ compile pfa
> 
>   dup dup ,             \ compile buffer size
> 
>   here 2 cells+ ,       \ pre-computed lower bound
> 
>   here 1 cells+ + 1- ,  \ pre-computed upper bound
> 
>   allot
> 
>   does>
> 
>   dup @ _bufPfa @ <> if
> 
>     dup @ _bufPfa !
> 
>     dup 1 cells+ @ _bufSize !
> 
>     dup 2 cells+ @ _lowBound !
> 
>     dup 3 cells+ @ _topBound !
> 
>   then
> 
>   4 cells+ ;
> 
> 
> 
> : sizeOf ( buffer -- u)
> 
>   \ report size of buffer
> 
>   drop _bufSize @ ;
> 
> 
> 
> : <>bounds ( address -- address flag)
> 
>   \ check if address is within buffer bounds
> 
>   dup dup  _lowBound @ >=  swap  _topBound @ <=  AND ;
> 
> 
> 
> : b@ ( address -- u)
> 
>   \ fetch a cell from the buffer address
> 
>   <>bounds if @ else true abort" Out of bounds in B@" then ;
> 
> 
> 
> : b! ( u address -- )
> 
>   \ write a cell to the buffer address
> 
>   <>bounds if ! else true abort" Out of bounds in B!" then ;
> 
> 
> 
> : bc@ ( address -- u)
> 
>   \ fetch a char from the buffer address
> 
>   <>bounds if c@ else true abort" Out of bounds in BC@" then ;
> 
> 
> 
> : bc! ( u address -- )
> 
>   \ write a char to the buffer address
> 
>   <>bounds if c! else true abort" Out of bounds in BC!" then ;
> 
> 
> 
> -------------------------
> 
> Tests:
> 
> 
> 
> 100 buffer fred
> 
> : test
> 
>   fred dup sizeOf 0 do
> 
>     i  over i + bc!
> 
>   loop drop ;
> 
> 
> 
> 999 fred 50 + b!
> 
> fred 50 + b@ .
> 
> 999 ok
> 
> 
> 
> fred 104 + bc@ .
> 
> Out of bounds in BC@

Hi!

A version:
---
: cell+  1 cells + ;
: $@  ( a -- ca u )  dup @ swap cell+ swap ;
\
\ cache map:
\ |_bufPFA|_bufSize|_lowBound|_topBound|
\
create cache 4 cells allot
cache   cell+   constant _bufSize
cache 2 cells + constant _lowBound
cache 3 cells + constant _topBound

: buffer  ( size "name -- ; -- a )
  create dup , allot
  does>  dup cache @ <>
         IF   dup cache !
              dup $@ _bufSize ! _lowBound !
              dup $@ + 1- _topBound !
         THEN cell+
;
---
Have a nice day,
humptydumpty

[toc] | [prev] | [next] | [standalone]

#15342

"Mark Wills" <markrobertwills@yahoo.co.uk> wrote in message
news:86bccc99-b093-42c4-ae50-39c308b66254@p12g2000vbm.googlegroups.com...
> While writing about memory buffer overruns in a different thread
> earlier today, I was inspired to have a bash at writing some
> code that would allow safe read/write access to memory buffers.
>
> I came up with the code and wonder if it could be simplified or
> improved any.
>
> It's very simple. When a buffer is created, the first four cells
> are reserved for the following:
> * The pfa of the buffer (i'll explain in a minute)
> * The size of the buffer in bytes
> * The lowest legally accessible address
> * The highest legally accessible address
>

The problem here is the same issue that C has with pointers.  It's the same
reason why Java removed pointers for safety.  C has the issue of determining
whether a pointer points to or into a valid C object, or not.

If you have an address in Forth, you don't know if it points into a buffer,
which buffer, or somewhere else, unless you check the ranges of _all_ known
buffers.  So, let's say you've got over 50 buffers and an address.  Does the
address point into a buffer and which one?  You'll need a dictionary of
buffer entries.  You need to loop through all of them for each address to
determine if the address is within the range of one of the buffers.  As you
demonstrated, this only works _if_ you already know which buffer an address
points into.

The other option is to not allow pointers to point into an object.  Then,
the pointer always points to the object's header, or to invalid data.  But,
that complicates accessing data within an object, such as a character from a
string, or an item from a structure.

Of course, if you don't realize it, what you're doing is implementing part
of a type system.  You're storing all the relevant info a compiler would
need to check the type, but doing so just for your buffer.


Rod Pemberton

[toc] | [prev] | [next] | [standalone]

#15345

Mark Wills wrote:

> While writing about memory buffer overruns in a different thread
> earlier today, I was inspired to have a bash at writing some
> code that would allow safe read/write access to memory buffers.
> 
> I came up with the code and wonder if it could be simplified or
> improved any.
> 
> It's very simple. When a buffer is created, the first four cells
> are reserved for the following:
> * The pfa of the buffer (i'll explain in a minute)
> * The size of the buffer in bytes
> * The lowest legally accessible address
> * The highest legally accessible address
>
> It's possible to compute the last two items on the fly of
> course, but I chose to do the math once and store the computed
> result, rather than compute it on each buffer access, for
> performance reasons.

I'm happy with your style.  For performance reasons, please store two 
things: start address an size, let's say into _start and _bound.  Then 
you can do

Variable _start
Variable _bound

: bound-error ( -- )  true abort" out of bound" ;

: ?bound ( addr [size] -- )
  ]] dup _start @ - _bound @ Literal - u<= IF [[ ; immediate
: bound? ( -- )  ]] ELSE  bound-error  THEN [[ ; immediate

: b@ ( addr -- x )  [ cell ] ?bound @ bound? ;
: b! ( x addr -- )  [ cell ] ?bound ! bound? ;
: bc@ ( addr -- c )  [ 1 ] ?bound c@ bound? ;
: bc! ( c addr -- )  [ 1 ] ?bound c! bound? ;

And for checking whether to update?

: buffer: ( size "name" -- )
  Create dup , allot
  Does> ( -- addr ) dup @ _bound ! cell+ dup _start ! ;

You should run some benchmarks which one is faster - IMHO just writing 
two variables and not checking if they have already been used is faster.  
And you definitely should check close to the range ends (checking is 
done with 64 bit Gforth):

100 buffer: foo
foo 92 + b@ drop  ok
foo 93 + b@ drop 
:21: out of bound
foo 93 + >>>b@<<< drop
Backtrace:
$7F91EF5C3E20 throw 
$7F91EF61F788 c(abort") 
$7F91EF61FA50 bound-error 
foo 99 + bc@ drop  ok
foo 100 + bc@ drop 
:23: out of bound
foo 100 + >>>bc@<<< drop
Backtrace:
$7F91EF5C3E20 throw 
$7F91EF61F788 c(abort") 
$7F91EF61FBE0 bound-error 

If you test with bigForth/MINOS, bulk postponing is not compiled into 
the main part, so you need to define

: [[ ; \ token to end bulk-postponing
: ]] BEGIN  >in @ ' ['] [[ <> WHILE  >in ! postpone postpone  REPEAT
    drop ; immediate

before.  Well, I really should put that in the core, it is so useful for 
this kind of thing.  The check I do breaks if your buffer is actually 
too small for one cell...

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

[toc] | [prev] | [next] | [standalone]

#15348

Bernd Paysan wrote:
> I'm happy with your style.

There's a not missing here... I'm actually not that happy with your 
style...

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

[toc] | [prev] | [next] | [standalone]

#15358

Bernd Paysan <bernd.paysan@gmx.de> writes Re: Buffer access with bounds checking...
[..]
> You should run some benchmarks which one is faster - IMHO just writing 
> two variables and not checking if they have already been used is faster.  
> And you definitely should check close to the range ends (checking is 
> done with 64 bit Gforth):
[..]

Your scheme is faster, but not much.

#100000000 VALUE #times

: stest ( -- )
	CR ." (Paysan) #times = " #times U>D (n,3)
	CR ."   protected: " timer-reset 
	  #times 0 ?DO  foo #88 + b@ 
			foo #80 + b@ +
			foo #72 + b@ +
			foo #64 + b@ + DROP  
		  LOOP 
	.elapsed

	CR ." UNprotected: " timer-reset 
	  #times 0 ?DO  foo #88 + @ 
			foo #80 + @ +
			foo #72 + @ +
			foo #64 + @ + DROP  
		  LOOP 
	.elapsed ;

FORTH> stest
#times = 100,000,000
  protected: 1.273 seconds elapsed.
UNprotected: 0.345 seconds elapsed. ok


Mark's:

100 buffer fred
: test
  fred dup sizeOf 0 do
    i  over i + bc!
  loop drop ;

: stest2 ( -- )
	CR ." (Wills) #times = " #times U>D (n,3)
	CR ."   protected: " timer-reset 
	  #times 0 ?DO  fred #88 + b@ 
			fred #80 + b@ +
			fred #72 + b@ +
			fred #64 + b@ + DROP  
		  LOOP 
	.elapsed

	CR ." UNprotected: " timer-reset 
	  #times 0 ?DO  fred #88 + @ 
			fred #80 + @ +
			fred #72 + @ +
			fred #64 + @ + DROP  
		  LOOP 
	.elapsed ;

FORTH> stest2
#times = 100,000,000
  protected: 1.827 seconds elapsed.
UNprotected: 0.720 seconds elapsed. ok

-marcel

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.forth

csiph-web