Appending definition to another definition

[program...@gmail.com]

I am trying to append the execution behavior of one word to another word. This will makes things clearer.

Say you have myword like this
: myword
word1
word2
;

I need to add another word to the end of myword so it acts like this

: myword
word1
word2
word3
;

I could do this by hand, but I need to do this in code. Any body know of a way I could append code to a definition?

[Jason Damisch]

Is this what you are looking foar?

: word1 ;
: word2 ;
: word3 ;

variable <word3> ['] noop <word3> !

: myword word1 word2 <word3> @ execute ;

Then you can turn word3 on and off by storing word3 or noop into <word3>

Jason

[Jason Damisch]

> I could do this by hand, but I need to do this in code. Any body know of a way I could append code to a definition?

Actually, there is insufficient information here to answer your question, but if you elaborate, we can probably figure something out.

Jason

[program...@gmail.com]

What I am looking for is a word that allows me to add to the end of a definition. Something like this would be nice:

WordAppender myword wordToBeCalledAtEnd

[Jason Damisch]

>
> WordAppender myword wordToBeCalledAtEnd

But why? What are you trying to achieve in the context of the surrounding code? Maybe there is another route or way.

If

[teammem...@gmail.com]

> Is this what you are looking foar?
>
>
>
> : word1 ;
>
> : word2 ;
>
> : word3 ;
>
>
>
> variable <word3> ['] noop <word3> !
>
>
>
> : myword word1 word2 <word3> @ execute ;
>
>
>
> Then you can turn word3 on and off by storing word3 or noop into <word3>
>
>
>
> Jason

Thanks for trying but I need to add cleanup code to the end of a word that I will not have access to. What this cleanup code will do is free memory allocated by another word that was called at the beginning of a word. It want the end result to be like this:

: someword
allocateMemory

...words in between

releaseMemory
;

The thing is my allocateMemory word is going to need cleaning up after. So by adding a word that does that, I can release the memory that isn't used any more. I want to be able to automatically add my releaseMemory word to the end of any word that uses my allocateMemory word. This would make things nice and tidy.

[Jason Damisch]

> The thing is my allocateMemory word is going to need cleaning up after. So by adding a word that does that, I can release the memory that isn't used any more. I want to be able to automatically add my releaseMemory word to the end of any word that uses my allocateMemory word. This would make things nice and tidy.

What about something like this

: MemoryStuff
allocateMemory <dohicky> @ execute releaseMemory ;

Then when you call your words, do it this way

' George <dohicky> ! MemoryStuff
' Henry <dohicky> ! MemoryStuff
' Philip <dohicky> ! MemoryStuff
' Steven <dohicky> ! MemoryStuff

This could even be cleaned up somewhat as far as code aesthetics

: MemoryStuff ( xt -- )
allocateMemory execute releaseMemory ;

' Steven MemoryStuff

[program...@gmail.com]

That does look close to what I need. I think it should be possible to alter the dictionary in some way so that an execution token can be added to the end of a definition. Any body know the forth dictionary well enough to do something like this?

[Jason Damisch]

> That does look close to what I need. I think it should be possible to alter the dictionary in some way so that an execution token can be added to the end of a definition. Any body know the forth dictionary well enough to do something like this?

But think about it. The space needs to exist at the end of the definition in the RAM to be able to append the word, or you will clobber the header of the next word which is consecutive in the memory. The alternative to this would be to move all of the words up in memory, but then you would also need to relink all of the words to all of the other words. This would be very complicated. If it is a subroutine threaded system, it gets even more hairy.

Is there a simple way to do what you need?

Jason

[program...@gmail.com]

I doubt there is a simple way to do what I need. An easy thing to do is to not release the memory - let it turn into wasted space. I am not an expert in Forth, so hopefully I am wrong.

[Jason Damisch]

> I doubt there is a simple way to do what I need. An easy thing to do is to not release the memory - let it turn into wasted space. I am not an expert in Forth, so hopefully I am wrong.

I don't know the overall structure of your application. A cheap solution might come to you after you sleep for the night, and then wake up in the morning with a fresh start to the problem.

How much memory is involved? How many times do you allocate memory?

[Paul Rubin]

program...@gmail.com writes:
> I doubt there is a simple way to do what I need. An easy thing to do
> is to not release the memory

You could wrap the old word:

: foo 1 . 2 . 3 . ;
' foo \ push xt of foo
create foo , does> @ execute 4 . \ now redefine it

foo \ prints 1 2 3 4

[Gerry Jackson]

You can't simply append a call to another word in ANS Forth but you can
redefine myword using your syntax e.g.

: wordappender >in @ >r : r> >in ! ' compile, ' compile, postpone ; ;

: myword dup + ;
1 myword . \ displays 2
wordappender myword .
1 myword \ displays 2

--
Gerry

[Rod Pemberton]

<program...@gmail.com> wrote in message
news:ef305924-1126-4b36...@googlegroups.com...

Isn't this what VALUE and TO or DEFER and IS are for?

(Jason did the a similar thing using 'variable'.)


Is the orignal 'myword' already in the dictionary? I.e., you can't change
it at all. Or, are you definining both "myword's"?

If you're defining the original 'myword', you could insert a no-operation
for 'word3' and change it later to another word. Actually, you could use
VALUE TO or DEFER IS to change 'word1' 'word2' or 'word3'. So, 'word3'
could initially be a no-operation, but later be changed to a word.


With DEFER and IS:

: NOP ;

DEFER A
DEFER B
DEFER C

: WORDX A B C ;
' DUP IS A
' + IS B
' NOP IS C

2 WORDX .

<4> OK.

' 1+ IS C

2 WORDX .

<5> OK.


With VALUE and TO:

: NOP ;

0 VALUE A
0 VALUE B
0 VALUE C

: A0 A EXECUTE ;
: B0 B EXECUTE ;
: C0 C EXECUTE ;

: WORDX A0 B0 C0 ;

' DUP TO A
' + TO B
' NOP TO C

2 WORDX .

<4> OK.

' 1+ TO C

2 WORDX .

<5> OK.


As you can see, WORDX is either one or two or three Forth words, depending
on how you set A, B, and C.

HTH,


Rod Pemberton

[Arnold Doray]

On Sun, 29 Jul 2012 22:43:09 +0100, Gerry Jackson wrote:
>>
>> What I am looking for is a word that allows me to add to the end of a
>> definition. Something like this would be nice:
>>
>> WordAppender myword wordToBeCalledAtEnd
>
> You can't simply append a call to another word in ANS Forth but you can
> redefine myword using your syntax e.g.
>
> : wordappender >in @ >r : r> >in ! ' compile, ' compile, postpone ; ;
>
> : myword dup + ;
> 1 myword . \ displays 2
> wordappender myword .
> 1 myword \ displays 2

Wouldn't a simpler way to accomplish this be a redefinition?

: a 1 ; ok
: a a 2 ; redefined a ok
a ok
.S <2> 1 2 ok

Am I missing something?

Cheers,
Arnold

[Gerry Jackson]

Yes of course, but that is effectively what my definition does. I was
simply responding to the OP's request.

> Am I missing something?

It seems so. The OP asked:

<quote>Something like this would be nice:

WordAppender myword wordToBeCalledAtEnd</quote>

Whether it's sensible or not depends on his circumstances.

--
Gerry

[Mark Wills]

> The thing is my allocateMemory word is going to need cleaning up after. So by adding a word that does that, I can release the memory that isn't used any more. I want to be able to automatically add my  releaseMemory word to the end of any word that uses my allocateMemory word. This would make things nice and tidy.- Hide quoted text -
>
> - Show quoted text -

"I want to be able to automatically add my releaseMemory word to the
end of any word that uses my allocateMemory word. This would make
things nice and tidy."

Hmmm... Okay, make allocateMemory an immediate compiling word, and re-
define ; to compile the releaseMemory word into the definition for
you:

variable _releaseMemory
false _releaseMemory !

: (allocateMemory) <code to do memory allocation> ;

: allocateMemory true _releaseMemory ! postpone (allocateMemory) ;
immediate

: (releaseMemory) <code to do memory de-allocation> ;

: ; _releaseMemory @ if
postpone (releaseMemory)
false _releaseMemeory !
then postpone ;
; immediate


So, now you (or your user) must explicitly call allocateMemory in a
word, but he doesn't need to call releaseMemory - if allocateMemory
was referenced in the colon-definition then a call to (releaseMemory)
will automatically be compiled for him.

Is that the sort of thing you were looking for? If I understood your
requirements correctly then I think the above, or some variation
thereof should help to get you on the right track. Just shout out if
anything in the above is unclear.

However, you might want to consider a different version of colon for
words that need allocation and de-allocation, to differentiate them
more clearly from 'normal' definitions. Something like a: and ;a for
words that require memory allocation/de-allocation:

a: some-word <code for the word> ;a

The above could be built something like this:

: a: postpone : postpone (allocateMemory) ;
: ;a postpone (releaseMemory) postpone ; ; immediate

Now there is no requirement for the variable _releaseMemory. You would
use it like this:

a: fred <some code here> ;a

And the memory allocation and de-allocation calls are automatically
compiled into the definition for you. The fact that the word is
created with a: tells you that it's a memory allocating word. Just
document your application code so that others (or you after 12
months!) will know what is special about words defined with a:

That's probably the road that I would go down if I had a similar
requirement.

HTH

[Arnold Doray]

On Sun, 29 Jul 2012 11:58:12 -0700, programmingkidx wrote:
>
> What I am looking for is a word that allows me to add to the end of a
> definition. Something like this would be nice:
>
> WordAppender myword wordToBeCalledAtEnd

Have you considered simply re-defining the word?

Eg

(myword is in your library code, and you want to add a "finalization"
routine at the back of it)

: wordToBeCalledAtEnd ... ; \ Your custom cleanup routines.

: myword myword wordToBeCalledAtEnd ; \ you word + cleanup

This would only work for all calls to MYWORD downstream of the re-
definition. It would not of course work for calls internal to the
library. Changing internal library code is probably not a good idea.

Cheers,
Arnold

[Elizabeth D. Rather]

If you aren't allocating the memory repeatedly, it shouldn't be a
problem. The normal practice in Forth is either to permanently ALLOT a
buffer that can be used repeatedly, or ALLOCATE and FREE within the same
word, for space being used temporarily.

Cheers,
Elizabeth

--
==================================================
Elizabeth D. Rather (US & Canada) 800-55-FORTH
FORTH Inc. +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[Hugh Aguilar]

On Jul 30, 1:13 am, Mark Wills <markrobertwi...@yahoo.co.uk> wrote:
> However, you might want to consider a different version of colon for
> words that need allocation and de-allocation, to differentiate them
> more clearly from 'normal' definitions. Something like a:  and ;a for
> words that require memory allocation/de-allocation:
>
> a: some-word <code for the word> ;a
>
> The above could be built something like this:
>
> : a: postpone :  postpone (allocateMemory) ;
> : ;a  postpone (releaseMemory)  postpone ; ; immediate
>
> Now there is no requirement for the variable _releaseMemory. You would
> use it like this:
>
> a: fred <some code here> ;a
>
> And the memory allocation and de-allocation calls are automatically
> compiled into the definition for you. The fact that the word is
> created with a: tells you that it's a memory allocating word. Just
> document your application code so that others (or you after 12
> months!) will know what is special about words defined with a:

This is the best solution so far.

Actually though, what you are asking for doesn't make much sense. What
is that allocated memory supposed to be used for? Why do you expect
every A: word to need the same amount of memory?

If you want some memory temporarily allocated within a colon word,
just use local variables --- they get allocated at the beginning of
the colon word and semi-colon deallocates them at termination --- just
what you seem to be asking for.

If one-cell local variables aren't adequate, such as if you need a
record or an array, then I would still use a local variable but I
would ALLOCATE some memory (the size of the record or array) at the
beginning and put the address in the local, and then FREE it at the
end. If you are going to have such a great number of these kinds of
words that you want to automate the process, then you could write
macros similar to what Mark did above.

You can use MACRO: from my novice package
(http://www.forth.org/novice.html) rather than raw POSTPONE and
EVALUATE to improve readability:

macro: ]stuff
] literal dup alloc locals| stuff stuff-size |
stuff stuff-size erase ;

macro: stuff>
stuff dealloc ;

: test
[ 10 ]stuff
cr ." adr: " stuff .
cr ." size: " stuff-size .
cr ." contents:"
stuff stuff-size bounds do cr I c@ . loop
stuff> ;

This is somewhat different than Mark's example. I don't incorporate :
and ; into my macros. I just provide ]STUFF and STUFF> that bracket
the code. Inside of these, you have the STUFF local variable that
points to a block of memory that is as large as you specified (10
bytes in the TEST example), and the STUFF-SIZE local variable that is
the size of the block of memory (10 in the TEST example). If you run
TEST, the adr will be different every time, the size will be 10, and
the contents will be 10 zeros. Like this:

test
adr: 41213732
size: 10
contents:
0
0
0
0
0
0
0
0
0
0 ok

All of this seems way more complicated than anything that I would
normally do when writing a program. What are you trying to accomplish?
If you told us what your application is, we would be able to help you
better. What you are asking for doesn't seem to make much sense. What
is that memory going to be used for?

[Mark Wills]

On Jul 31, 8:42 am, Hugh Aguilar <hughaguila...@yahoo.com> wrote:
>
> All of this seems way more complicated than anything that I would
> normally do when writing a program. What are you trying to accomplish?
> If you told us what your application is, we would be able to help you
> better. What you are asking for doesn't seem to make much sense. What

> is that memory going to be used for?- Hide quoted text -

>
> - Show quoted text -

Agreed. A general description of the problem you are trying to solve
might help us to come up with an alternative solution. Forth is
sufficiently old that most eggs were cracked a long time ago!

Dynamic memory allocation in Forth applications is relatively rare, as
far as I'm aware. Most Forth applications (especially those running on
embedded systems) get by just fine with statically allocated memory,
often allocated when the application starts up.

If you can re-design your application such that it can take advantage
of statically allocated memory then it could potentially benefit from
a performance increase; with dynamically allocated memory comes the
issues of memory fragmentation and garbage collection, which one
doesn't have to worry about with statically allocated memory.

Apologies if this is all bread and butter to you already.

[Hugh Aguilar]

On Jul 31, 1:05 am, Mark Wills <markrobertwi...@yahoo.co.uk> wrote:
> Dynamic memory allocation in Forth applications is relatively rare, as
> far as I'm aware. Most Forth applications (especially those running on
> embedded systems) get by just fine with statically allocated memory,
> often allocated when the application starts up.

Actually, I use dynamic memory allocation all of the time. :-) This is
because I use lists a lot, and all of those nodes are dynamically
allocated. I agree though, that micro-controller programs won't
generally use the heap much if at all. The novice package is for
desktop-computer programming.

In the novice package, I don't use ALLOT, but instead I use CONCRETE-
ALLOCATE. The advantage is that ALLOCATION works for blocks of memory
provided by both CONCRETE-ALLOCATE and ALLOCATE. Also, FREE works for
both (it does nothing with a CONCRETE-ALLOCATE block that is in the
dictionary) --- this is a huge improvement over typical Forth in which
FREE will crash if it is given a block of memory in the dictionary
rather than the heap. The purpose of this compatibility between
CONCRETE-ALLOCATE and ALLOCATE is so that a program can first be
written to use ALLOCATE at run-time. Later on, it may be discovered
that some of that work can be done at compile-time. It is easy to
switch from run-time (putting the nodes on the heap) to compile-time
(putting the nodes in the dictionary) with minimal modification of the
source-code of the program. I do this in my slide-rule program if you
want to see an example.

[rickman]

On Sunday, July 29, 2012 5:00:00 PM UTC-4, (unknown) wrote:
>
> I doubt there is a simple way to do what I need. An easy thing to do is to not release the memory - let it turn into wasted space. I am not an expert in Forth, so hopefully I am wrong.

I wonder if there is a business model in reclaiming the wasted space in old PCs. I know there are some businesses that reclaim the precious metals from PCs, why not wasted space? Just think of all the bits that have been wasted all these years and could be reclaimed, reused and recycled!

Otherwise where does all that memory go?

Rick

[George Hubert]

On Tuesday, July 31, 2012 9:55:56 AM UTC+1, Hugh Aguilar wrote:
--- this is a huge improvement over typical Forth in which FREE will crash if it is given a block of memory in the dictionary rather than the heap.

Which Forth are you talking about. The Standard states that FREE either succeeds and returns zero or fails returning non-zero: anything else is clearly a bug. Perhaps you should try reading the Standard instead of coming up with incorrect statements.

George Hubert

[Andrew Haley]

George Hubert <george...@yahoo.co.uk> wrote:

> The Standard states that FREE either succeeds and returns zero or
> fails returning non-zero: anything else is clearly a bug.

Not exactly. The standard doesn't say anything about what happens if
you fail to honour your side of the contract, which is "a-addr shall
indicate a region of data space that was previously obtained by
ALLOCATE or RESIZE."

Andrew.

[George Hubert]

On Tuesday, July 31, 2012 6:38:13 PM UTC+1, Andrew Haley wrote:
> George Hubert <george...@yahoo.co.uk> wrote: > The Standard states that FREE either succeeds and returns zero or > fails returning non-zero: anything else is clearly a bug. Not exactly. The standard doesn't say anything about what happens if you fail to honour your side of the contract, which is "a-addr shall indicate a region of data space that was previously obtained by ALLOCATE or RESIZE." Andrew.

Surely:

14.4.1.2 Ambiguous conditions
no additional requirements.

implies that there aren't any ambiguous conditions, which undefined behaviour in the event of a-addr not coming from ALLOCATE implies. Anyway it doesn't state it will crash, as Hugh said.

George Hubert

[hughag...@yahoo.com]

Everything in my novice package is ANS-Forth compliant. You don't know what you are talking about.

[Andrew Haley]

George Hubert <george...@yahoo.co.uk> wrote:
> On Tuesday, July 31, 2012 6:38:13 PM UTC+1, Andrew Haley wrote:
>> George Hubert <george...@yahoo.co.uk> wrote:
> The Standard states that FREE either succeeds and returns zero or
> fails returning non-zero: anything else is clearly a bug.
>
> Not exactly. The standard doesn't say anything about what happens if
> you fail to honour your side of the contract, which is "a-addr shall
> indicate a region of data space that was previously obtained by
> ALLOCATE or RESIZE."
>
> Andrew.
>
> Surely:
>
> 14.4.1.2 Ambiguous conditions
> no additional requirements.
>
> implies that there aren't any ambiguous conditions,

No it doesn't: it says there are no additional requirements. That
"shall" is important.

Andrew.

[hughag...@yahoo.com]

On Wednesday, August 1, 2012 2:34:18 AM UTC-7, Andrew Haley wrote:
> George Hubert <george...@yahoo.co.uk> wrote:
>
> > On Tuesday, July 31, 2012 6:38:13 PM UTC+1, Andrew Haley wrote:
>
> >> George Hubert <george...@yahoo.co.uk> wrote:
>
> > The Standard states that FREE either succeeds and returns zero or
>
> > fails returning non-zero: anything else is clearly a bug.
>
> >
>
> > Not exactly. The standard doesn't say anything about what happens if
>
> > you fail to honour your side of the contract, which is "a-addr shall
>
> > indicate a region of data space that was previously obtained by
>
> > ALLOCATE or RESIZE."
>
> >
>
> > Andrew.
>
> >
>
> > Surely:
>
> >
>
> > 14.4.1.2 Ambiguous conditions
>
> > no additional requirements.
>
> >
>
> > implies that there aren't any ambiguous conditions,
>
>
>
> No it doesn't: it says there are no additional requirements. That
>
> "shall" is important.
>
>
>
> Andrew.

There are actually quite a lot of ways to crash a Forth system that involve failure to honor your side of the contract. lol

In regard to FREE, the standard (14.6.1.1605) says: "If the operation fails, the ior is an implementation-defined I/O result code."

That is completely useless! If the standard said what code would be returned in the event that the address was not originally provided by ALLOCATE or RESIZE, then the programmer could do something about it. As it is, we don't know what caused the failure, which makes it unreasonable to do anything other than just abort the program with an unhelpful error message: "FREE has failed, but we don't know why." So it doesn't really matter if FREE crashes outright, or if it returns an uninformative error-code and the application program has to abort --- from the user's perspective, the Forth program has just crashed.

I have said many many times that the failure of ANS-Forth was due to the standard being too wishy-washy. What kind of standard uses the term "implementation defined" as a crutch throughout? What exactly has been standardized?

My novice package version of FREE just assumes that the size cell is negative for CONCRETE-ALLOCATE and positive for ALLOCATE. It doesn't catch application bugs in which the address came from neither CONCRETE-ALLOCATE or ALLOCATE. In that case, I just abort with an unhelpful error message. This is assuming that the system FREE itself doesn't just crash, which is a possibility.

The whole point of my system is that if you have code that frees nodes when they are no longer needed (you should or you will have memory leaks) this code will continue to work even if your nodes are actually in the dictionary rather than the heap. AFAIK, nobody has understood this feature yet. In my slide-rule program, I generate the common scales (D etc.) at compile-time because they are certainly going to be needed, but the uncommon scales I generate at run-time only if they are needed.

[Coos Haak]

Op Wed, 1 Aug 2012 03:27:41 -0700 (PDT) schreef hughag...@yahoo.com:

> In regard to FREE, the standard (14.6.1.1605) says: "If the operation
> fails, the ior is an implementation-defined I/O result code."
>
> That is completely useless! If the standard said what code would be
> returned in the event that the address was not originally provided by
> ALLOCATE or RESIZE, then the programmer could do something about it. As
> it is, we don't know what caused the failure, which makes it
> unreasonable to do anything other than just abort the program with an
> unhelpful error message: "FREE has failed, but we don't know why." So it
> doesn't really matter if FREE crashes outright, or if it returns an
> uninformative error-code and the application program has to abort ---
> from the user's perspective, the Forth program has just crashed.

If the implementation returns a sensible I/O result code, the program could
warn the programmer that she made a mistake to use FREE on an invalid
address. That's where I/O result codes are for. If your implementation
does not do that, throw it away.

--
Coos

CHForth, 16 bit DOS applications
http://home.hccnet.nl/j.j.haak/forth.html

[Coos Haak]

Op Tue, 31 Jul 2012 23:52:24 -0700 (PDT) schreef hughag...@yahoo.com:

lamenielache!

[Paul Rubin]

Coos Haak <chf...@hccnet.nl> writes:
> If the implementation returns a sensible I/O result code, the program
> could warn the programmer that she made a mistake to use FREE on an
> invalid address.

I don't see how to determine if the address is invalid without an awful
lot of overhead and hassle, remembering in some auxiliary structure
where all the valid pointers are. The auxiliary structure would itself
have to be dynamically allocated since its required size can't be known
in advance. I guess you could mark each allocated region with a magic
random number that the user program isn't allowed to inspect, so the
chance of the user data containing the same number by accident would be
very low.

[Jason Damisch]

All of this seems like an incredibly huge pain in the butt, I would solve the problem by not doing that, and totally rethinking the problem.

Jason

[Mark Wills]

On Aug 1, 4:02 pm, Jason Damisch <jasondami...@yahoo.com> wrote:
> All of this seems like an incredibly huge pain in the butt, I would solve the problem by not doing that, and totally rethinking the problem.
>
> Jason

I was very surprised to see that FREE takes an address as its
argument. If I had to design my own, I think ALLOCATE would return a
token (or 0 for fail) and the token is used for FREE. I guess it could
be argued that the address could be considered a token.

What happens if you FREE an address which wasn't ALLOCATEd?

[Anton Ertl]

George Hubert <george...@yahoo.co.uk> writes:
>On Tuesday, July 31, 2012 6:38:13 PM UTC+1, Andrew Haley wrote:

>> George Hubert <george...@yahoo.co.uk> wrote: > The Standard states th=
>at FREE either succeeds and returns zero or > fails returning non-zero: any=
>thing else is clearly a bug. Not exactly. The standard doesn't say anything=
> about what happens if you fail to honour your side of the contract, which =
>is "a-addr shall indicate a region of data space that was previously obtain=

>ed by ALLOCATE or RESIZE." Andrew.
>
>Surely:
>
>14.4.1.2 Ambiguous conditions

>no additional requirements.=20

>
>implies that there aren't any ambiguous conditions

Or not any additional ones.

>which undefined behavio=
>ur in the event of a-addr not coming from ALLOCATE implies. Anyway it doesn=

>'t state it will crash, as Hugh said.

But crash it does, on a number of systems (see below). And I don't
see a reliable and efficient way to prevent this in all cases.

- anton
-----------------------------------------------------
VFX Forth for Linux IA32
© MicroProcessor Engineering Ltd, 1998-2009

Version: 4.40 [build 0404]
Build date: 7 December 2009

Free dictionary = 7922527 bytes [7736kb]


here free
CS=0023 DS=002B ES=002B SS=002B FS=0000 GS=0063
EAX=0800:0000 EBX=F7FB:4FF4 ECX=0893:4EB1 EDX=0000:0000
ESI=F7FB:6160 EDI=080B:9CA1 EBP=0893:4F94 ESP=0893:4F7C
EIP=F7ED:631C EFLAGS=0001:0206
--- RS top ---
$0000:0009
$080B:61C9 ADD-HISTORY-LINE
$0800:0000
$0000:0000
$0894:4FC0
$0893:4FA0
$0894:4FB0
$0804:AADD NXCALL
Signal number SIGSEGV
at address F7ED:631C, probably in * outside dictionary *

Press E to exit, R to restart, other to continue:

----------------------------------------------------------
[c7:~:31707] sf
SwiftForth i386-Linux 3.2.1 28-Dec-2009
here free *** glibc detected *** sf: free(): invalid pointer: 0x080801b1 ***
Aborted

----------------------------------------------------------
Gforth 0.6.2, Copyright (C) 1995-2003 Free Software Foundation, Inc.
Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license'
Type `bye' to exit
0 free . 0 ok
here free . *** glibc detected *** gforth: free(): invalid pointer: 0x00007f85c1f28898 ***
======= Backtrace: =========
/lib/libc.so.6[0x7f85c2767948]
/lib/libc.so.6(cfree+0x76)[0x7f85c2769a56]
gforth(engine+0x2584)[0x406674]
gforth(go_forth+0x174)[0x40f914]
gforth(main+0x153)[0x4106e3]
/lib/libc.so.6(__libc_start_main+0xe6)[0x7f85c27121a6]
gforth[0x404059]
======= Memory map: ========
...
Aborted.

The Gforth behaviour is wrong. The Forth system should not terminate
(it normally does not terminate even if it executes an illegal
instruction).

- 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 2012: http://www.euroforth.org/ef12/

[Paul Rubin]

an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> But crash it does, on a number of systems (see below). And I don't
> see a reliable and efficient way to prevent this in all cases.

If you're using malloc as the underlying manager, to allocate a block of
n cells, get a block of n+1 cells from malloc. Lightly scramble the
address of this block and store the result in cell 0, then return the
address of block 1. On free, make sure that the stuff before block 1
has the right contents. Obviously since forth has no memory protection,
a malicious program could subvert this scheme, but it's not likely to
happen by accident.

[Anton Ertl]

Not what I consider reliable, especially on 32-bit systems. Good
enough for debugging purposes (and probably the libc malloc used by
Gforth and SwiftForth used such an approach), but if "not crashing"
was guaranteed, it would not be good enough.

On a 32-bit system I would expect it to fail for one out of 2^32 FREEs
of non-ALLOCATEd addresses. And if not-crashing was guaranteed, there
would likely be programs that make use of this guarantee and FREE
arbitrary addresses with abandon, and such a program would find the
failing case eventually. And if you don't expect such programs, why
ask for that guarantee?

[Paul Rubin]

an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> On a 32-bit system I would expect it to fail for one out of 2^32 FREEs
> of non-ALLOCATEd addresses.

Using two or three cells would decrease that likelihood exponentially.
The alternative is to remember every pointer ALLOCATE has returned until
it is freed. I guess that could be tolerable. Have cell 0 point back
to a table entry owned by the allocator, where the table entry has the
allocated block's address, until it is freed. The table would have to
expand dynamically, maybe using a tree structure, etc. Blecch.

> And if not-crashing was guaranteed, there would likely be programs
> that make use of this guarantee and FREE arbitrary addresses with
> abandon,

Yeah, that would be a pretty horrendous way to program, but I suppose
issuing a guarantee would invite it.

[George Hubert]

On Wednesday, August 1, 2012 4:09:07 PM UTC+1, Anton Ertl wrote:
> George Hubert <george...@yahoo.co.uk> writes: >On Tuesday, July 31, 2012 6:38:13 PM UTC+1, Andrew Haley wrote: >> George Hubert <george...@yahoo.co.uk> wrote: > The Standard states th= >at FREE either succeeds and returns zero or > fails returning non-zero: any= >thing else is clearly a bug. Not exactly. The standard doesn't say anything= > about what happens if you fail to honour your side of the contract, which = >is "a-addr shall indicate a region of data space that was previously obtain= >ed by ALLOCATE or RESIZE." Andrew. > >Surely: > >14.4.1.2 Ambiguous conditions >no additional requirements.=20 > >implies that there aren't any ambiguous conditions Or not any additional ones. >which undefined behavio= >ur in the event of a-addr not coming from ALLOCATE implies. Anyway it doesn= >'t state it will crash, as Hugh said. But crash it does, on a number of systems (see below). And I don't see a reliable and efficient way to prevent this in all cases. - anton ----------------------------------------------------- VFX Forth for Linux IA32 © MicroProcessor Engineering Ltd, 1998-2009 Version: 4.40 [build 0404] Build date: 7 December 2009 Free dictionary = 7922527 bytes [7736kb] here free CS=0023 DS=002B ES=002B SS=002B FS=0000 GS=0063 EAX=0800:0000 EBX=F7FB:4FF4 ECX=0893:4EB1 EDX=0000:0000 ESI=F7FB:6160 EDI=080B:9CA1 EBP=0893:4F94 ESP=0893:4F7C EIP=F7ED:631C EFLAGS=0001:0206 --- RS top --- $0000:0009 $080B:61C9 ADD-HISTORY-LINE $0800:0000 $0000:0000 $0894:4FC0 $0893:4FA0 $0894:4FB0 $0804:AADD NXCALL Signal number SIGSEGV at address F7ED:631C, probably in * outside dictionary * Press E to exit, R to restart, other to continue: ---------------------------------------------------------- [c7:~:31707] sf SwiftForth i386-Linux 3.2.1 28-Dec-2009 here free *** glibc detected *** sf: free(): invalid pointer: 0x080801b1 *** Aborted ---------------------------------------------------------- Gforth 0.6.2, Copyright (C) 1995-2003 Free Software Foundation, Inc. Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license' Type `bye' to exit 0 free . 0 ok here free . *** glibc detected *** gforth: free(): invalid pointer: 0x00007f85c1f28898 *** ======= Backtrace: ========= /lib/libc.so.6[0x7f85c2767948] /lib/libc.so.6(cfree+0x76)[0x7f85c2769a56] gforth(engine+0x2584)[0x406674] gforth(go_forth+0x174)[0x40f914] gforth(main+0x153)[0x4106e3] /lib/libc.so.6(__libc_start_main+0xe6)[0x7f85c27121a6] gforth[0x404059] ======= Memory map: ======== ... Aborted. The Gforth behaviour is wrong. The Forth system should not terminate (it normally does not terminate even if it executes an illegal instruction). - anton -- M. Anton Ertl

Both Win32forth and Bigforth (at least on Windows XP) return non-zero iors, so it's seems that some systems don't crash. Certainly the Swiftforth and VFX behaviours at least return control to the terminal and give an error message so Programmers know that FREE caused the error and can use that information for debugging (I'd describe it as ABORTing rather than crashing). Certainly the assertation that it WILL crash (rather than may) is plain wrong. I would certainly expect a programmer to know how the forth he uses for testing and debugging to know how their system behaves in order to make sense of the information (or lack of it).

Anyway as both you and Andrew have pointed out I was wrong.

George Hubert

[George Hubert]

On Wednesday, August 1, 2012 6:15:10 PM UTC+1, Paul Rubin wrote:
> an...@mips.complang.tuwien.ac.at (Anton Ertl) writes: > On a 32-bit system I would expect it to fail for one out of 2^32 FREEs > of non-ALLOCATEd addresses. Using two or three cells would decrease that likelihood exponentially. The alternative is to remember every pointer ALLOCATE has returned until it is freed. I guess that could be tolerable. Have cell 0 point back to a table entry owned by the allocator, where the table entry has the allocated block's address, until it is freed. The table would have to expand dynamically, maybe using a tree structure, etc. Blecch. > And if not-crashing was guaranteed, there would likely be programs > that make use of this guarantee and FREE arbitrary addresses with > abandon, Yeah, that would be a pretty horrendous way to program, but I suppose issuing a guarantee would invite it.

Using a linked list where the cell is linked in by ALLOCATE is more sensible. FREE checks if it's in the list and fails if not or unlinks the the block and releases it. RESIZE is similar but relinks the block after resizing. It's actually how w32F does it. It also allows debugging aids like
.MALLOCS
Link-Addr Rel-Addr Bytes HeapAddr Type
--------- -------- -------- -------- ----
00E50020 00E50030 1,257,472 00150000
0015AFC0 0015AFD0 32,768 00150000
00157090 001570A0 332 00150000
00159DE0 00159DF0 132 00150000
00CC0020 00CC0030 1,048,576 00150000
00159C90 00159CA0 293 00150000
00157228 00157238 260 00150000
00156840 00156850 2,084 00150000
--------- -------- -------- -------- ----
Total allocated 2,341,917
ok

George Hubert

[Paul Rubin]

George Hubert <george...@yahoo.co.uk> writes:
> Using a linked list where the cell is linked in by ALLOCATE is more
> sensible. FREE checks if it's in the list and fails if not or unlinks

If FREE has to linearly search a list of arbitrary size on every call, I
wouldn't describe that as an efficient solution.

[George Hubert]

On Wednesday, August 1, 2012 8:02:28 PM UTC+1, Paul Rubin wrote:
> George Hubert <george...@yahoo.co.uk> writes: > Using a linked list where the cell is linked in by ALLOCATE is more > sensible. FREE checks if it's in the list and fails if not or unlinks If FREE has to linearly search a list of arbitrary size on every call, I wouldn't describe that as an efficient solution.

Then add 2 cells prior to the data and used a binary tree with the memory address itself (rather than a pointer) as the key, then it only costs an extra 2 cells per allocation. Certainly it would be more efficient than 2 pointers and having to expand the allocation table. All the dictionary needs is a pointer to the starting node (VARIABLE or VALUE).

George Hubert

[j...@rainbarrel.com]

> I was very surprised to see that FREE takes an address as its
>
> argument. If I had to design my own, I think ALLOCATE would return a
>
> token (or 0 for fail) and the token is used for FREE. I guess it could
>
> be argued that the address could be considered a token.
>
>
>
> What happens if you FREE an address which wasn't ALLOCATEd?

Diaperglu Forth doesn't have FREE and ALLOCATE. It instead uses a buffer management system where a token is returned which is actually a 0 based index like you are suggesting. This means Diaperglu can tell when someone tries to free a buffer that doesn't exist. It also keeps track of free buffers.

What about adding a buffer management system to the Forth standard?

[j...@rainbarrel.com]

> > All of this seems way more complicated than anything that I would
> > normally do when writing a program. What are you trying to accomplish?
> > If you told us what your application is, we would be able to help you
> > better. What you are asking for doesn't seem to make much sense. What
> > is that memory going to be used for?- Hide quoted text -

> Agreed. A general description of the problem you are trying to solve
> might help us to come up with an alternative solution. Forth is
> sufficiently old that most eggs were cracked a long time ago!

Why not add more advanced dynamic memory allocation to the Forth Standard? Maybe something like string stacks?

Diaperglu Forth has had string stacks for a long time, and the latest version even supports local string variables which are automatically allocated and deallocated for you.

[Jason Damisch]

> Diaperglu Forth has had string stacks for a long time, and the latest version even supports local string variables which are automatically allocated and deallocated for you.

Diaperglu Forth is a funny name for a Forth, although I'm sure that the quality of the system is pretty good.

Jason

[hughag...@yahoo.com]

Using multiple magic-number signatures doesn't help! What happens if you try to FREE a block of memory more than once? The old magic numbers are still sitting there in memory most likely.

The big problem here is that everybody seems to be stuck on using GLIBC with its MALLOC and FREE. According to Anton Ertl, this is why my ALLOCATION was rejected; because C doesn't have it and so neither can Forth. This is despite the fact that the allocated size is obviously stored internally already. Now we are talking about keeping a list or a tree of all the allocated blocks of memory. This is despite the fact that this information is obviously stored internally already.

Oh, come on! Write your own heap and do a good job of it, with ALLOCATION available and FREE working properly. Stop relying on GLIBC. If you think that GLIBC is so wonderful, then why not just program in C and forget about Forth?

This reliance on GLIBC is an albatross around your neck. Gforth is a disgrace to Forth --- abandon Gforth! --- your decision to support C-based Forth systems has brought you only bad luck!

I'm not going to support C-based systems in Straight Forth. My goal is to provide a *better* development system than C, so that C programmers will abandon C and switch to Forth --- I'm not trying to provide a Forth that is just a pathetic imitation of C, which is what Gforth is.

[Bernd Paysan]

Anton Ertl wrote:
> The Gforth behaviour is wrong. The Forth system should not terminate
> (it normally does not terminate even if it executes an illegal
> instruction).

We could set the environment variable MALLOC_CHECK_ to 1. Then glibc
prints a diagnostic output on stderr, but does not terminate the
program. Or catch SIGABRT (we do, but quit on SIGABRT instead of throw,
as SIBABRT is intented to do that). If we set MALLOC_CHECK_ to 2, it
will only abort, and print no diagnostics.

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

[Bernd Paysan]

Bernd Paysan wrote:
> We could set the environment variable MALLOC_CHECK_ to 1.

Or, as Hugh suggested, we could implement our own memory management
code, e.g. take the code from bigForth (I did my own memory management
in bigForth, because the Atari ST's OS-based memory management was piss-
poor).

It does an awful lot for the 20 blocks it is implemented in, a lot more
than just allocate, resize, and free.

[hughag...@yahoo.com]

On Wednesday, August 1, 2012 6:45:47 AM UTC-7, Coos Haak wrote:
> Op Wed, 1 Aug 2012 03:27:41 -0700 (PDT) schreef hughag...@yahoo.com:
> > In regard to FREE, the standard (14.6.1.1605) says: "If the operation
> > fails, the ior is an implementation-defined I/O result code."
> >
> > That is completely useless!
>

> If the implementation returns a sensible I/O result code, the program could
> warn the programmer that she made a mistake to use FREE on an invalid
> address. That's where I/O result codes are for. If your implementation
> does not do that, throw it away.

The idea is that a program will work the same on any standard-compliant system. That is what the word "standard" means.

[Aleksej Saushev]

There's a natural linear order on addresses.


--
HE CE3OH...

[hughag...@yahoo.com]

Well, as your tag says: "If you want it done right, you have to do it yourself." It is always a bad idea to rely on OPC --- that is what script kiddies do --- they look like geniuses for a while, but then their ignorance trips them up and they fall on their faces. Similarly, I can beat most computer programs at Go --- they play in a dull and unimaginative manner --- they have heuristics but they don't have understanding.

In the days of the Atari ST and its MC68K, a heap was pretty easy. Now with all of these cache systems in use, it is more complicated. It is hardly the kind of problem that should daunt the intrepid Forth-200x members though. Also, there are plenty of people on CLAX who can help if necessary --- it is not like this is the first time anybody has ever implemented a heap.

[Paul Rubin]

Aleksej Saushev <as...@inbox.ru> writes:
>> If FREE has to linearly search a list of arbitrary size on every call,

> There's a natural linear order on addresses.

How do you suggest 1) finding an address in the list, even if they're
in linear order; 2) inserting a new address into the list?

[Aleksej Saushev]

What is the point of maintaining a list when you can maintain at least
balanced tree with faster lookups and insertions?? You can implement
self-balancing tree the way you like with minimal effort.


--
HE CE3OH...

[Paul Rubin]

Aleksej Saushev <as...@inbox.ru> writes:
> What is the point of maintaining a list when you can maintain at least
> balanced tree with faster lookups and insertions?? You can implement
> self-balancing tree the way you like with minimal effort.

I don't understand what point you were making about the linear ordering
of addresses in this case. Structures like self-balancing trees are
fancier than what one normally sees in Forth, in my limited knowledge.
The scheme I suggested earlier of a pointer next to each allocated
region, pointing back to a table of allocated addresses, seems a lot
simpler than a self-balancing tree.

[A. K.]

Yep. We once had a heap in extra RAM. ALLOCATE was just taking the next
free space of sufficient size between chained blocks by circular memory
search. No garbage collection, never ever any problems, blazingly fast.

[Paul Rubin]

"A. K." <a...@nospam.org> writes:
> Yep. We once had a heap in extra RAM. ALLOCATE was just taking the
> next free space of sufficient size between chained blocks by circular
> memory search. No garbage collection, never ever any problems,
> blazingly fast.

A classic first-fit allocator from Knuth vol 1, probably just right for
the sorts of 16-bit environments where Forth was historically important,
but not really suitable for modern hardware with potentially millions or
billions of live objects.

[hughag...@yahoo.com]

I have a self-balancing tree in my novice package.

I don't think that your scheme with the table is all that efficient. If your "table" is an array, then inserting and deleting in the middle is slow, and a binary search isn't any faster than a tree descent.

I haven't given a whole lot of thought to the subject of heap design, although I think that it is fairly easy. Searching for nodes isn't really the time-critical aspect of the code. The difficult part is allocating the nodes so they use the caches efficiently. You guys have immediately begun speculating on algorithms for node searching, which is really the most trivial aspect of the problem.

A little bit of research wouldn't hurt --- heaps have been in use since before I was born --- somebody likely knows something about implementing them.

A heap is a somewhat interesting problem --- maybe I will implement one for the next novice-package release. :-)

[Anton Ertl]

Bernd Paysan <bernd....@gmx.de> writes:
>Anton Ertl wrote:
>> The Gforth behaviour is wrong. The Forth system should not terminate
>> (it normally does not terminate even if it executes an illegal
>> instruction).
>
>We could set the environment variable MALLOC_CHECK_ to 1.

Setting an environment variable is not a good style for communicating
within a process, because it will also influence child processes.

However, while we are considering workarounds for this misfeature of
glibc, we could call mcheck().

A relatively easy-to-implement approch would be to supply a function
that converts the mcheck_status into a THROW value and then THROWs.

But given the interface of FREE it would be nicer to have FREE return
the throw value as ior (and leave it to the application to throw or do
something else). I don't see a clean way to implement that, though.

Implementing ALLOCATE based on lower-level stuff would also be
possible (another implementation is part of my garbage collector), but
seems overkill, and worse, I doubt that our own implementation would
be as efficient.

[Anton Ertl]

Paul Rubin <no.e...@nospam.invalid> writes:
>an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> On a 32-bit system I would expect it to fail for one out of 2^32 FREEs
>> of non-ALLOCATEd addresses.
>
>Using two or three cells would decrease that likelihood exponentially.

Two or three cells extra for just this purpose is not what I consider
efficient. And it would still be probabilistic.

>The alternative is to remember every pointer ALLOCATE has returned until
>it is freed. I guess that could be tolerable. Have cell 0 point back
>to a table entry owned by the allocator, where the table entry has the
>allocated block's address, until it is freed. The table would have to
>expand dynamically, maybe using a tree structure, etc. Blecch.

That's better: It still costs two cells per ALLOCATEd block, but at
least it's not probabilistic.

I would not use a tree for the table, just a big block; then the check
for validity can be performed in constant time. Getting the big block
may be a problem in some environments, but with a large address space
(64 bits) and an OS that supports memory overcommitment it's a
non-issue. In smaller environments one might grow that block towards
bigger addresses and grow the ALLOCATEd memory towards smaller
addresses.

Still, the space overhead of that approach is considerable for small
ALLOCATEd blocks, which are frequent.

I thought a little more about this problem and remembered that I have
already solved it, in the allocator used in my garbage collector. The
garbage collector is conservative, so I need a way to check if a value
X can be the address of an allocated block.

I solved the problem as follows: for each grain (of, say, 8 bytes),
there are two bits (stored elsewhere): One says if the grain is at the
start of a block (this provides information about the length of the
block), the other says whether the block starting at the grain is
occupied or free. These bits are stored in separate areas, which has
similar issues as the table discussed above.

The check whether an address points to an ALLOCATEd block can be
performed in constant time. The space overhead is 3% for 8-byte
granularity. To achieve the same space efficiency with a system that
needs three cells per block (one for the block size and two for the
two pointers mentioned above), the average block size would have to be
96 cells.

One could also combine the two systems: Have an allocator for blocks
up to 96 cells that uses my approach and one for larger blocks that
uses your approach; put the small blocks in one area of the address
space that does not contain any big blocks, then the address check can
just decide which check to use with a simple WITHIN check.

Implementing all that is left as an exercise to the reader:-)

[Paul Rubin]

an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> I would not use a tree for the table, just a big block; then the check
> for validity can be performed in constant time.

You mean a preallocated big block that could hold all the pointers
that might potentially be allocated all at once? You might have
to reserve 100's of MB, or even GB. Even though it might not allocate
real pages, it still seems awful.

A tree isn't needed: I think a linked list of blocks is good enough.
Just prepend new blocks to the linked list and remember where the newest
one is. When you delete a pointer from the middle of some block, pop
and copy the most recent pointer from the newest block, into the
now-freed slot. If that makes the block become empty, release it after
following its link to get to the previous block. All these operations
are constant time (you do need a way to allocate these blocks...).

> I thought a little more about this problem and remembered that I have
> already solved it, in the allocator used in my garbage collector. The
> garbage collector is conservative, so I need a way to check if a value
> X can be the address of an allocated block.

Of course that is also probabilistic (the definition of a conservative
gc).

[Bernd Paysan]

Anton Ertl wrote:
> I thought a little more about this problem and remembered that I have
> already solved it, in the allocator used in my garbage collector. The
> garbage collector is conservative, so I need a way to check if a value
> X can be the address of an allocated block.
>
> I solved the problem as follows: for each grain (of, say, 8 bytes),
> there are two bits (stored elsewhere): One says if the grain is at the
> start of a block (this provides information about the length of the
> block), the other says whether the block starting at the grain is
> occupied or free. These bits are stored in separate areas, which has
> similar issues as the table discussed above.

Actually, for small blocks on a 64 bit system I'd use one area for each
size. No overhead required except the mapped space. If the block is in
the 8-byte-chunks space, it is an 8 byte chunk.

Each thread has its own starting point to allocate and its own free list
(this is completely lock-free). I'd leave the NUMA stuff to the copy-
on-write part for anonymously mmapped pages. I'd say if thread A
reclaims memory allocated from thread B, it ends up in thread A's free
list, and the user gets what he deservers.

IMHO, there are four sorts of objects you want to claim memory for:

* small fixed-size objects which you never will resize, but which need
very fast allocate and free - these should go into one-region-per-size,
one-starting-point-per-thread buckets. These fixed-size objects could
be under the regime of a garbage colletor (it makes most sense here).

* small variable-sized objects which need some way of compaction
(editable strings), as they change their size quite often. These should
go into pages (allocated per-thread), which can be compacted
individually, and they have a backlink pointer which gets updated on
compaction. These objects are under the regime of a compactor, they are
explicitly deallocated (e.g. when the object that points to them dies).
These objects know their length - they are strings.

* large objects should be allocated and freed in page granularities,
using mmap. No compaction necessary if you only allow power-of-two
aligned starting points.

* large, purgeable objects should be treated the same way, but may be
deallocated if the system senses a need for that (some operating systems
tell you when they are short in memory).

I'm not that sure about the strings-to-be-compacted, as it is just as
easy to keep them in the fixed-size buckets, and move them completely
into another region if they change size.

[Anton Ertl]

Paul Rubin <no.e...@nospam.invalid> writes:
>an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> I would not use a tree for the table, just a big block; then the check
>> for validity can be performed in constant time.
>
>You mean a preallocated big block that could hold all the pointers
>that might potentially be allocated all at once?

Yes, but some variations are possible:

1) Start small, and double the size when it becomes too small; this
may incur the costs of relocation, though (either redo the pointers
when the size is doubled, or store offsets into the table instead of
pointers).

2) Use an expandable memory area (e.g., sbrk() in Unix, and mmap for
the data blocks).

>You might have
>to reserve 100's of MB, or even GB. Even though it might not allocate
>real pages, it still seems awful.

Why?

Unused virtual memory costs very little. Let's see what 1TB costs:

[~:77867] time gforth -e bye

real 0m0.007s
user 0m0.008s
sys 0m0.004s
[~:77868] time gforth -m 1T -e bye

real 0m0.007s
user 0m0.004s
sys 0m0.004s

I.e., time difference in the noise.

USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND
anton 6119 0.0 0.0 1073755196 1544 pts/0 S+ 16:17 0:00 gforth -m 1T
anton 6142 0.0 0.0 21564 1532 pts/0 S+ 16:18 0:00 gforth

And a whopping 12KB difference in resident set size.

The strategy is admittedly limited in the platforms it works on, but
on those platforms it's a good strategy.

>A tree isn't needed: I think a linked list of blocks is good enough.

In order to perform the check we need to determine if the validation
pointer points to an address in one of the blocks (otherwise you can
get false positives). If we keep the extra data in one block, we can
do this with a simple WITHIN. If we keep it in a tree, we need a tree
search (no longer constant time); if we keep it in a list, we need a
linear search (linear cost).

>> I thought a little more about this problem and remembered that I have
>> already solved it, in the allocator used in my garbage collector. The
>> garbage collector is conservative, so I need a way to check if a value
>> X can be the address of an allocated block.
>
>Of course that is also probabilistic (the definition of a conservative
>gc).

The check is reliable. Of course success still does not guarantee
that the value is a pointer, so I could have just as well used a
probabilistic method that may produce false positives (but must not
produce false negatives), but I didn't; there would be no advantage.

[Alex McDonald]

On Aug 3, 2:58 pm, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

It works on Windows too.

The downside is; allocated but uncommitted memory is cheap, but
unallocated and committed memory is wasteful (for some definition of
wasteful; it increases the working set size for one and may result in
page copy-on-write operations in other processes). It takes effort &
an understanding of the relationship of pages to allocated blocks from
the allocator to do an uncommit since it can only be done on whole
pages.

[snipped]

[Anton Ertl]

Alex McDonald <bl...@rivadpm.com> writes:
>The downside is; allocated but uncommitted memory is cheap, but
>unallocated and committed memory is wasteful (for some definition of
>wasteful; it increases the working set size for one and may result in
>page copy-on-write operations in other processes). It takes effort &
>an understanding of the relationship of pages to allocated blocks from
>the allocator to do an uncommit since it can only be done on whole
>pages.

I don't know what you mean with "unallocated" in this context
(especially after the way you use "allocated" in the sentence before).
But if you want to reduce the amount of commited memory after a
reduction in the amount of live memory, you could mmap the unused
memory again (using MAP_FIXED), and the old mapping will be
overwritten and the old memory should be reclaimed. At least on POSIX
systems.

[Paul Rubin]

an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND
> anton 6119 0.0 0.0 1073755196 1544 pts/0 S+ 16:17 0:00 gforth -m 1T
> I.e., time difference in the noise.

> And a whopping 12KB difference in resident set size.

Arggghh... hmmm... I dunno... maybe it's legitimate but seeing a number
like that still makes me sit up in my chair. I wonder if a lot of page
tables get allocated in the kernel that don't count as user RSS. I'd
think it prevents the hardware address protection from catching most
stray pointers during debugging. I wonder if it affects the paging
behavior of other processes. It never occurred to me that allocating
such a region was even possible. Wow.

> In order to perform the check we need to determine if the validation

> pointer points to an address in one of the blocks... If we keep it in

> a tree, we need a tree search (no longer constant time)

Hmm, good point, though the tree can have large nodes (100's or 1000's
of pointers) so the number of levels will always be small, effectively
bounded by a constant. They will probably have better cache locality
than the allocated regions might often cost less to traverse than
getting to the freed region did.

Overall though it seems implausible that the Forth standard intended to
impose a requirement like this.

[Andrew Haley]

Paul Rubin <no.e...@nospam.invalid> wrote:
>
> Overall though it seems implausible that the Forth standard intended to
> impose a requirement like this.

I'm sure the TC intended no such thing. This discussion is just about
(IMO pointless) thoretical niceties.

Andrew.

[Anton Ertl]

Paul Rubin <no.e...@nospam.invalid> writes:
>an...@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND
>> anton 6119 0.0 0.0 1073755196 1544 pts/0 S+ 16:17 0:00 gforth -m 1T
>> I.e., time difference in the noise.
>> And a whopping 12KB difference in resident set size.
>
>Arggghh... hmmm... I dunno... maybe it's legitimate but seeing a number
>like that still makes me sit up in my chair. I wonder if a lot of page
>tables get allocated in the kernel that don't count as user RSS.

Maybe it's not shown in the RSS, but given that there is hardly any
increment in execution time (see below), it cannot be a lot; we see
nothing in the time results, so let's see if we can see more with
performance counters:

[~:77886] perfex -e 0x4100c0 -e 0x4200c0 gforth -e bye
tsc 17680590
event 0x004100C0@0 11816963
event 0x004200C0@1 1152795
[~:77887] perfex -e 0x4100c0 -e 0x4200c0 gforth -m 1T -e bye
tsc 17921088
event 0x004100C0@0 11818484
event 0x004200C0@1 1200593

An increase in cycles (tsc) by very little (same order of magnitude as
the noise), 1500 more instructions executed in user mode (0x4100c0),
and 48000 more instructions executed in system mode (0x4200c0). There
does not fit a lot in there.

And why should a lot of page tables get allocated? There's a lot of
sharing possible: The zeroed page can be shared, the first-level page
tables all pointing to that page can be shared, too, and so on.

>I'd
>think it prevents the hardware address protection from catching most
>stray pointers during debugging.

A few GB (or whatever) in an address space of 17179869184 GB will
prevent catching *most* stray pointers? Not in my experience. But if
you are worried about that you can first mmap the area with PROT_NONE,
and change the permissions when you actually need the pages for data.

>Hmm, good point, though the tree can have large nodes (100's or 1000's
>of pointers) so the number of levels will always be small, effectively
>bounded by a constant. They will probably have better cache locality
>than the allocated regions might often cost less to traverse than
>getting to the freed region did.

I cannot follow you here.

>Overall though it seems implausible that the Forth standard intended to
>impose a requirement like this.

Yes.

[Alex McDonald]

On Aug 3, 5:12 pm, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

> Alex McDonald <b...@rivadpm.com> writes:
> >The downside is; allocated but uncommitted memory is cheap, but
> >unallocated and committed memory is wasteful (for some definition of
> >wasteful; it increases the working set size for one and may result in
> >page copy-on-write operations in other processes). It takes effort &
> >an understanding of the relationship of pages to allocated blocks from
> >the allocator to do an uncommit since it can only be done on whole
> >pages.
>
> I don't know what you mean with "unallocated" in this context
> (especially after the way you use "allocated" in the sentence before).

I should have said "reserved" rather than "allocated" in the first
sentence; and "user allocated blocks that are freed" in the second.

[Aleksej Saushev]

I'm not sure that information that can be easily overwritten in case of
buffer overrun is useful for correctness check. Extra pointer, whether
appended or prepended to allocated block, can be easily overwritten.
Storing this information in a separate memory region gives more chances
to its survival.


--
HE CE3OH...

[program...@gmail.com]

Thank you so much. This is exactly what I wanted. Your code from the first part actually worked! A+ reply!