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

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

RESIZE boundary conditions

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

Contents

  RESIZE boundary conditions anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-05-15 11:26 +0000
    Re: RESIZE boundary conditions ruvim.pinka@gmail.com - 2016-05-15 06:46 -0700
      Re: RESIZE boundary conditions anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-05-15 17:08 +0000
    Re: RESIZE boundary conditions november.nihal@gmail.com - 2016-05-15 09:13 -0700
      Re: RESIZE boundary conditions Albert van der Horst <albert@cherry.spenarnc.xs4all.nl> - 2016-05-15 18:23 +0000
      Re: RESIZE boundary conditions anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-05-16 13:13 +0000
        Re: RESIZE boundary conditions Hans Bezemer <the.beez.speaks@gmail.com> - 2016-05-16 15:23 +0200
          Re: RESIZE boundary conditions anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-05-16 14:01 +0000
          Re: RESIZE boundary conditions hughaguilar96@gmail.com - 2016-05-16 14:14 -0700
    Re: RESIZE boundary conditions Albert van der Horst <albert@cherry.spenarnc.xs4all.nl> - 2016-05-15 18:13 +0000
      Re: RESIZE boundary conditions anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-05-16 10:32 +0000
        Re: RESIZE boundary conditions Albert van der Horst <albert@cherry.spenarnc.xs4all.nl> - 2016-05-16 22:38 +0000
    Re: RESIZE boundary conditions Hans Bezemer <the.beez.speaks@gmail.com> - 2016-05-16 14:54 +0200

#47141 — RESIZE boundary conditions

On most Forth systems RESIZE ( addr1 u -- addr2 ior) is implemented by
calling the C library's realloc(void *ptr, size_t size).  There are
at least two interesting boundary cases:

1) What if addr1=0?

The C99 and C11 C standards cover this clearly:

|If ptr is a null pointer, the realloc function behaves like the malloc
|function for the specified size.

That is useful: If there is a variable that contains an address for a
variable-size memory region, you can just initialize it to 0, and
everything will be fine.

The Forth standard requires that a-addr1 is "previously allocated by
ALLOCATE or RESIZE".

That means that one has to initialize the variable above with an
ALLOCATEd address for memory that will never be used, or
alternatively, always check for 0 before calling RESIZE.

Testing this with Gforth, SwiftForth, and VFX (on Linux), 0 50 RESIZE
produces an address and ior=0 on all of them.  So we might add the
provision for allowing addr1=0 to the standard as common practice.

2) What if u=0?

The Forth standard says nothing particular about this situation.
Given that 0 is sensible input, I expect that this should just work,
i.e., return ior=0; I don't care that much about the address in this
case.  However, all Forth systems I tested (Gforth (except my private
bug-fixed version), SwiftForth, and VFX) return a non-zero ior (VFX
also returns addr2=-1, while the standard requires addr2=addr1 in the
ior!=0 case).  Why is that?

C99 says:
|If the realloc function returns a null pointer when size is zero and
|ptr is not a null pointer, the object it pointed to has been freed.
|[...]
|The realloc function returns either a null pointer or a pointer to the
|possibly moved allocated space.

Now the glibc (Linux) realloc() frees the object and returns a null
pointer when you call realloc(...,0).  Apparently all three Forth
systems interpret that null pointer as indication of failure (like for
malloc()), not as a valid result for realloc(...,0).  But IMO they
should treat it as a valid result.

That brings me to my main question: Are there Forth programs that fail
if "addr 0 RESIZE" returns 0 0?

Anyway, the story is not yet at an end: C11 tightened the
specification of realloc().  It now says:

|The realloc function returns a pointer to the new object (which may
|have the same value as a pointer to the old object), or a null pointer
|if the new object could not be allocated.

So if the glibc realloc() implemented the C11 standard, the three
Forth systems would work as I expect them to even for "addr 0 resize".
But C99-compliant libcs will be around for quite some time yet, so we
have to work around that.  There are two possible workarounds:

1) Check for u=0 if the result of the realloc() is null, and in that
case, return 0 0.

2) Check for u=0, and in that case use free() and malloc() (or, on the
Forth level, FREE and ALLOCATE) instead of realloc().  At least glibc
returns a non-null pointer for malloc(0), although the C standards do
not clearly require that, either.  On the Forth level that workaround
would look like:

: resize ( addr1 u -- addr2 ior )
  dup if
    resize
  else
    drop dup if free then 0 allocate rot or
  then ;

The benefit of this variant is that it works also for Forth programs
that don't expect addr2=0.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2016: http://www.euroforth.org/ef16/

[toc] | [next] | [standalone]

#47145

On Sunday, May 15, 2016 at 3:36:37 PM UTC+3, Anton Ertl wrote:

> That brings me to my main question: Are there Forth programs that fail
> if "addr 0 RESIZE" returns 0 0?

It seems that standard program can FREE addr that is returned by RESIZE without additional checks. So if RESIZE can return ( 0 0 ),  "0 FREE" should return 0. Otherwise such standard program will fail on FREE.


--
Ruvim1

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

#47151

ruvim.pinka@gmail.com writes:
>On Sunday, May 15, 2016 at 3:36:37 PM UTC+3, Anton Ertl wrote:
>
>> That brings me to my main question: Are there Forth programs that fail
>> if "addr 0 RESIZE" returns 0 0?
>
>It seems that standard program can FREE addr that is returned by RESIZE without additional checks. So if RESIZE can return ( 0 0 ),  "0 FREE" should return 0. Otherwise such standard program will fail on FREE.

Good point.  Standard FREE does not specify an action of 0 FREE.  C99
and C11 specify for free(void *ptr):

|If ptr is a null pointer, no action occurs.

So given that most (all?) Forth systems implement FREE by calling
free(), this might be another place where we probably should tighten
the standard based on common practice.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2016: http://www.euroforth.org/ef16/

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

#47149

   addr1 = 0 , u = 0    ==> If resize can only act on memory previously set aside by allocate or resize, then addr1=0 doesn't make sense as malloc only returns a nil ptr if it's unsuccessful or if size is 0.

   addr1 = 0 , u > 0    ==> ( as above ) 

   addr1 > 0 , u = 0    ==> u = 0 doesnt make sense as you are asking it to resize nothing 

   addr1 > 0 , u > 0    ==> is not a boundary condition and hence not being considered.

I think u=0 is not an issue since you are asking to resize nothing, however addr1 = nil ptr should throw an ior.

NN 

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

#47155

On 2016-05-15, november.nihal@gmail.com <november.nihal@gmail.com> wrote:
>
> addr1 = 0 , u = 0 ==> If resize can only act on memory previously
set aside by allocate or resize, then addr1=0 doesn't make sense as
malloc only returns a nil ptr if it's unsuccessful or if size is 0.
>
>    addr1 = 0 , u > 0    ==> ( as above )
>
> addr1 > 0 , u = 0 ==> u = 0 doesnt make sense as you are asking it
to resize nothing

It makes sense. Suppose (e.g. in my disassembler) I've a number of lists that
are not used all the time. I could RESIZE them to zero at those times, and
then later RESIZE them to an applicable size. If RESIZE makes sense at all,
it'll occasionally make sense to RESIZE to zero.

>
> addr1 > 0 , u > 0 ==> is not a boundary condition and hence not
being considered.
>
> I think u=0 is not an issue since you are asking to resize nothing,
however addr1 = nil ptr should throw an ior.
>
> NN

Groetjes Albert

P.S. Please wrap your lines. My newsreader enforces standards, so
I had to wrap the lines for you.

--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#47189

november.nihal@gmail.com writes:
>
>   addr1 = 0 , u = 0    ==> If resize can only act on memory previously set aside by allocate or resize, then addr1=0 doesn't make sense as malloc only returns a nil ptr if it's unsuccessful or if size is 0.
>
>   addr1 = 0 , u > 0    ==> ( as above ) 

addr1=0 makes sense at the beginning.  If that works, you can just
initialize the address variable or field with 0 instead of doing some
dummy allocation.

>   addr1 > 0 , u = 0    ==> u = 0 doesnt make sense as you are asking it to resize nothing 

The case that institgated this thread is a string buffer that is
RESIZEd for the size of the string.  In case of an empty string, it
was resized with "0 RESIZE".  Given that an empty string makes sense,
so does 0 RESIZE.  And I am asking it to resize to 0 size.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2016: http://www.euroforth.org/ef16/

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

#47190

Anton Ertl wrote:

> The case that institgated this thread is a string buffer that is
> RESIZEd for the size of the string.  In case of an empty string, it
> was resized with "0 RESIZE".  Given that an empty string makes sense,
> so does 0 RESIZE.  And I am asking it to resize to 0 size.
Provided there is a word like "ALLOCATED" that returns the size of the
buffer (AFAIK it's not in ANS Forth). If not, you need a count byte anyway.

Hans Bezemer

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

#47194

Hans Bezemer <the.beez.speaks@gmail.com> writes:
>Anton Ertl wrote:
>
>> The case that institgated this thread is a string buffer that is
>> RESIZEd for the size of the string.  In case of an empty string, it
>> was resized with "0 RESIZE".  Given that an empty string makes sense,
>> so does 0 RESIZE.  And I am asking it to resize to 0 size.
>Provided there is a word like "ALLOCATED" that returns the size of the
>buffer (AFAIK it's not in ANS Forth). If not, you need a count byte anyway.

Sure, the length of the string ist stored along with the address
elsewhere in the case that instigated this thread, just as is normal
for the "c-addr u" representation.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2016: http://www.euroforth.org/ef16/

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

#47217

On Monday, May 16, 2016 at 6:23:32 AM UTC-7, The Beez wrote:
> Anton Ertl wrote:
> 
> > The case that institgated this thread is a string buffer that is
> > RESIZEd for the size of the string.  In case of an empty string, it
> > was resized with "0 RESIZE".  Given that an empty string makes sense,
> > so does 0 RESIZE.  And I am asking it to resize to 0 size.
> Provided there is a word like "ALLOCATED" that returns the size of the
> buffer (AFAIK it's not in ANS Forth). If not, you need a count byte anyway.
> 
> Hans Bezemer

I have ALLOCATION in the novice-package --- this provides the value that the memory-block was allocated for --- by comparison, ALLOCATED provides the value that was actually provided, which may be slightly larger (some heap implementations provide memory blocks rounded up to a 16-byte boundary).

ALLOCATION (or ALLOCATE) are useful for cloning nodes. In a data-structure such as a tree you may have nodes of different classes (typically all in one parent-child chain) and hence different sizes. With ALLOCATION all of these can be cloned --- it is not necessary to examine each node to determine what class each one is and what size it is --- the word CLONE-NODE (in LIST.4TH) works on any list; I don't need separate versions for every class of node that might be in the list.

I can allocate in either the heap or the dictionary. FREE can determine if the memory block it is given is in either the heap or the dictionary, and it does nothing if the memory block is in the dictionary. RESIZE can also determine if the memory block it is given is in either the heap or the dictionary, and it moves the data to the heap if the memory block is in the dictionary. This is useful because sometimes I want to generate a data-structure at compile-time and store it in the dictionary, rather than generate it at run-time and store it in the heap --- I may switch from one way to another --- with my system I can switch where a data-structure is stored, and all the code that accesses the data-structure (any FREE or RESIZE) will continue to work without being rewritten.

ALLOCATION is really necessary for OOP --- my whole novice-package relies heavily on OOP for general-purpose data-structures --- that is why ALLOCATION is important (ALLOCATED would also work).

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

#47153

On 2016-05-15, Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
<SNIP>
>
>: resize ( addr1 u -- addr2 ior )
>   dup if
>     resize
>   else
>     drop dup if free then 0 allocate rot or
>   then ;
>
> The benefit of this variant is that it works also for Forth programs
> that don't expect addr2=0.

My ALLOCATE implementation will always return addresses that are
in the linked list of blocks, and 0 clearly is not.
However a length of zero leads to problems.
If a block is resized to zero, it is considered up for garbage collection.
If it is then resized to anything other than zero I'm in big trouble
because the address were I want to put the the new size may now belong
to something different.

You made me panick, but now I think I can cure this by
: resize   1 MAX <old code> ;

Thanks for making me rethink through this.

>
> - anton

Groetjes Albert

--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#47185

Albert van der Horst <albert@cherry.spenarnc.xs4all.nl> writes:
>: resize   1 MAX <old code> ;

Yes, a much simpler solution than mine.  UMAX would be more
appropriate than MAX, though.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2016: http://www.euroforth.org/ef16/

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

#47224

On 2016-05-16, Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> Albert van der Horst <albert@cherry.spenarnc.xs4all.nl> writes:
>>: resize   1 MAX <old code> ;
>
> Yes, a much simpler solution than mine.  UMAX would be more
> appropriate than MAX, though.

I've stopped worrying about sizes larger than 9223372036854775807

>
> - anton

Groetjes Albert

--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#47188

Anton Ertl wrote:

In 4tH there are several implementations, one paragraph based and one
implemented as a linked list. Both handle the situation differently:

- The paragraph based one simply allocates a full paragraph and returns OK;
- The linked list based one doesn't consider it a valid request and returns
ERROR.

An invalid pointer is always considered an error. None of these uses C.

Hans Bezemer

[toc] | [prev] | [standalone]

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

csiph-web