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

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

Relocatable Blocks

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

Contents

  Relocatable Blocks Ian van Breda <igvb@btopenworld.com> - 2013-08-25 20:21 +0100
    Re: Relocatable Blocks Paul Rubin <no.email@nospam.invalid> - 2013-08-25 14:04 -0700
      Re: Relocatable Blocks Ian van Breda <igvb@btopenworld.com> - 2013-08-29 19:55 +0100
    Re: Relocatable Blocks albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-08-26 11:34 +0000
      Re: Relocatable Blocks Hans Bezemer <the.beez.speaks@gmail.com> - 2013-08-26 14:58 +0200
        Re: Relocatable Blocks Hans Bezemer <the.beez.speaks@gmail.com> - 2013-08-26 15:30 +0200
        Re: Relocatable Blocks anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-08-26 14:33 +0000
          Re: Relocatable Blocks Ian van Breda <igvb@btopenworld.com> - 2013-08-29 20:22 +0100
    Re: Relocatable Blocks Mark Wills <markrobertwills@yahoo.co.uk> - 2013-08-26 07:08 -0700

#25396 — Relocatable Blocks

Most modern operating systems make used of one or more heaps to collect
transient data items.  This is done by means of handles, i.e. indirect
addresses, which point to relocatable blocks for access on the heap.  This
allows the size of a block to be changed, moving the block when necessary,
but the handle remains the same.

Relocatable blocks are very useful for structures whose size is not known
beforehand, particularly for stacks and queues and certain types of object
structures.  In Mas OS 9 only windows records are kept in non-relocatable
blocks; the other data structures are held in relocatable blocks.

For embedded systems, relocatable blocks can be accomplished by placing the
block in the Forth data space and moving it explicitly when the size is
changed but, again, it is necessary to use indirect addressing for
reference.

I suggest that the equivalent definitions for ALLOCATE, FREE and RESIZE be
defined in the standard.

NEW-HANDLE ( u -- hndl ior)
Attempt to allocate a relocatable block of size u address units on the heap.
The initial content of the allocated space is undefined.  Attempts to create
a free block of the requested size, including compacting the heap zone, if
necessary.
   If the allocation succeeds, ior is returned as zero.  If it has not been
possible to allocate a block of the required size, ior is the
implementation-defined error result code.

FREE-HANDLE ( hndl -- ior)
Dispose of a relocatable block, given its handle.  Returns a zero if the
operation was performed correctly, returns a non-zero if there has been an
error.

RESIZE-HANDLE ( hndl u -- ior)
Changes the logical size of the relocatable block, given a handle and
required size.  Returns zero ior if successful.  If it has not been possible
to allocate a block of the required size, ior is the implementation-defined
result code.

I have used relocatable blocks in my Forth dictionary, along the lines
outlined in Crafting a Compiler (Fischer, el al).  Particularly, allowing
the dictionary to be case sensitive or not, as required.

An addition, it allows words not use in a running system to be discarded.
For my system, there are a fair number of word that are not relevant to
application code - various Mac OS Traps, a number of subroutines and a large
number of OS data structures - which can be discarded in a precompiled
system.

There are compiler directives for this: GLOBAL causes definition headers to
be marked as visible in a running system up to the next LOCAL; LOCAL (not to
be confused with LOCALS| ) which sets a flag that marks subsequent
definition headers as used only during compilation up to the next GLOBAL;
INVISIBLE discards all LOCAL headers from the dictionary (but not their
code!).  For example, I have a dictionary of 2480 words but in a running
system this drops to 1120 for a fully pre-compiled ANS system (plus other
items), from a minimal kernel after applying INVISIBLE.

It is important to note that the purpose here is not to reduce memory usage
but instead to simplify the dictionary and avoiding cluttering in it up with
words not needed in a working system (dictionary entropy/pollution).

This means that LOCAL headers are not included on WORDS.  I also use a
definition that only gives that TASK-WORDS for a compiled application.
Also, there is switch that allows WORDS to work either in chronological or
alphabetical order.

Ian van Breda

[toc] | [next] | [standalone]

#25397

Ian van Breda <igvb@btopenworld.com> writes:
> I suggest that the equivalent definitions for ALLOCATE, FREE and RESIZE be
> defined in the standard...
> NEW-HANDLE ( u -- hndl ior)..
> FREE-HANDLE ( hndl -- ior)..
> RESIZE-HANDLE ( hndl u -- ior)..

There doesn't seem to be a way specified to access data in a relocatable
block--are you saying the application should just treat hndl as
something like an indirect pointer that can change at any time?  How is
that supposed to interact with multitasking?

Do you really need dynamic resizing for Forth stacks?  I thought very
deep stacks weren't really in the Forth spirit.  In any case, since only
the top few stack elements are directly accessible, resize can be done
completely behind the scenes, by moving the deeper elements off to some
other place in memory, keeping the top elements at fixed addresses.

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

#25466

Paul Rubin wrote on 25/08/2013 22:04:
> 
> There doesn't seem to be a way specified to access data in a relocatable
> block--are you saying the application should just treat hndl as
> something like an indirect pointer that can change at any time?  How is
> that supposed to interact with multitasking?
> 
> Do you really need dynamic resizing for Forth stacks?  I thought very
> deep stacks weren't really in the Forth spirit.  In any case, since only
> the top few stack elements are directly accessible, resize can be done
> completely behind the scenes, by moving the deeper elements off to some
> other place in memory, keeping the top elements at fixed addresses.

The relocatable blocks are held in a 'heap', a more flexible form of storage
mechanism than in a stack.  Usually, each task may have its own heap,
although that may not be necessary in a particular case.

Typically it is used for storing data objects which have life-times that
last longer than a stack, such as a word processing document or a stellar
spectrum, which needs to be manipulated in various ways.

During the progress of a program, many data objects may be allocated and
freed and may be even resized.  This may happen at any time and in any
order, leaving gaps in the heap.

The term 'handle' was used in both Mac OS, in its 'Classic' form, and in
Windows.  Control of the relocatable blocks was done behind the scenes,
including moving that data internally, e.g. compacting a heap if it proves
to be necessary to make space for new data.

More recently, handles have been replaced by pointers but the idea is the
same.  See 'Crafting a Compiler', p.500-511, 2010, under 'Heap Management'.


Albert van der Horst wrote on 26/08/2013 12:34:

> This all seems pretty useless without words to
> address into the blocks that are allocated.

Point taken!  Obviously you require things like H@ ( hndl offset -- x) and
H! ( x hndl offset -- ) for extracting and storing values in a relocatable
block, given a handle and an offset within a relocatable block.

Also a definition like HDUMP ( handl start u -- ) which dumps part of a
relocatable block, starting at a specified offset and given a number of
bytes to be displayed.

I use a Smalltalk-type Collection, which includes stacks, especially for the
Forth dictionary headers.  Data are placed in a stack frame for transferring
to a relocatable block.  Similarly, data can be extracted from a relocatable
block and placed on the parameter stack in the form of a stack-frame for
subsequent processing.

Ian

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

#25411

In article <CE4017C0.3A79%igvb@btopenworld.com>,
Ian van Breda  <igvb@btopenworld.com> wrote:
>Most modern operating systems make used of one or more heaps to collect
>transient data items.  This is done by means of handles, i.e. indirect
>addresses, which point to relocatable blocks for access on the heap.  This
>allows the size of a block to be changed, moving the block when necessary,
>but the handle remains the same.
>
>Relocatable blocks are very useful for structures whose size is not known
>beforehand, particularly for stacks and queues and certain types of object
>structures.  In Mas OS 9 only windows records are kept in non-relocatable
>blocks; the other data structures are held in relocatable blocks.
>
>For embedded systems, relocatable blocks can be accomplished by placing the
>block in the Forth data space and moving it explicitly when the size is
>changed but, again, it is necessary to use indirect addressing for
>reference.
>
>I suggest that the equivalent definitions for ALLOCATE, FREE and RESIZE be
>defined in the standard.
>
>NEW-HANDLE ( u -- hndl ior)
>Attempt to allocate a relocatable block of size u address units on the heap.
>The initial content of the allocated space is undefined.  Attempts to create
>a free block of the requested size, including compacting the heap zone, if
>necessary.
>   If the allocation succeeds, ior is returned as zero.  If it has not been
>possible to allocate a block of the required size, ior is the
>implementation-defined error result code.
>
>FREE-HANDLE ( hndl -- ior)
>Dispose of a relocatable block, given its handle.  Returns a zero if the
>operation was performed correctly, returns a non-zero if there has been an
>error.
>
>RESIZE-HANDLE ( hndl u -- ior)
>Changes the logical size of the relocatable block, given a handle and
>required size.  Returns zero ior if successful.  If it has not been possible
>to allocate a block of the required size, ior is the implementation-defined
>result code.

This all seems pretty useless without words to
address into the blocks that are allocated.

>Ian van Breda
>

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]

#25414

Albert van der Horst wrote:

> In article <CE4017C0.3A79%igvb@btopenworld.com>,
> This all seems pretty useless without words to
> address into the blocks that are allocated.
True. Having made a simple VM block system myself, the problem is not to
generate or load handles, but making memory access fairly transparent -
especially when it crosses block borders - in which case you have to
transparently load more than one block, unless you take other precautions.

And if you want to make the whole thing reloadable, you have to reserve some
blocks to maintain the whole allocation map.

Hans Bezemer

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

#25415

Hans Bezemer wrote:
For those who are interested, here is the code (for gForth). You cannot
allocate more than B/BUF address units per VBUFFER: using this code.

Note: only slightly tested.

Hans Bezemer

1024 constant b/buf

create vallot 0 ,
  does> 
  over b/buf min over @ dup rot + b/buf / b/buf * max rot over + rot !
;

: vbuffer: create vallot , does> @ b/buf /mod block + ;
                                       \ some convenience words..
: vplace place update ;                \ you may solve this another way
: +vplace +place update ;
: v! ! update ;

s" myfile.scr" open-blocks

 32 chars vbuffer: s1
128 chars vbuffer: s2
128 chars vbuffer: s3
512 chars vbuffer: s4
  1 cells vbuffer: n1
100 chars vbuffer: s5
256 chars vbuffer: s6
  1 cells vbuffer: n2

s" This is the end" s1 vplace          \ which span several blocks
1111 n2 v!
s1 count type cr
n2 @ . cr
s1 count type cr
s" My only friend" s1 vplace
2222 n1 v!
s1 count type cr                       \ now check their values
n2 @  . cr
s" , the end" s1 +vplace
n2 @  . cr
s1 count type cr
n1 @ . cr

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

#25418

Hans Bezemer <the.beez.speaks@gmail.com> writes:
>Albert van der Horst wrote:
>
>> In article <CE4017C0.3A79%igvb@btopenworld.com>,
>> This all seems pretty useless without words to
>> address into the blocks that are allocated.
>True. Having made a simple VM block system myself, the problem is not to
>generate or load handles, but making memory access fairly transparent -
>especially when it crosses block borders - in which case you have to
>transparently load more than one block, unless you take other precautions.

Either you have misunderstood what Ian van Breda proposes or I have.
My understanding is that he proposes a MacOS style (pre MacOS X)
handle system for explicit main (RAM) memory management (i.e., an
alternative to ALLOCATE FREE RESIZE), no disk/flash blocks involved.

The difference from ALLOCATE FREE RESIZE is that the memory block
returned by NEW-HANDLE can be moved around by the memory management
library.  This was useful in old MacOS, which did not have virtual
memory at first.  In other OSs like non-ancient versions of Unix
virtual memory is used in various ways that mostly eliminate the needs
that led to handles in MacOS.

One problem with handles is that addresses into the block referenced
by the handle are very short-lived, so you have to start addressing
from the handle for pretty much every access.

- 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 2013: http://www.euroforth.org/ef13/

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

#25467

Anton Ertl on 26/08/2013 15:33:
> 
> Either you have misunderstood what Ian van Breda proposes or I have.
> My understanding is that he proposes a MacOS style (pre MacOS X)
> handle system for explicit main (RAM) memory management (i.e., an
> alternative to ALLOCATE FREE RESIZE), no disk/flash blocks involved.
> 
> The difference from ALLOCATE FREE RESIZE is that the memory block
> returned by NEW-HANDLE can be moved around by the memory management
> library.  This was useful in old MacOS, which did not have virtual
> memory at first.  In other OSs like non-ancient versions of Unix
> virtual memory is used in various ways that mostly eliminate the needs
> that led to handles in MacOS.
> 
> One problem with handles is that addresses into the block referenced
> by the handle are very short-lived, so you have to start addressing
> from the handle for pretty much every access.
> 

Admittedly, the term 'handle' has mostly been superseded by pointers.  With
or without virtual memory, you still need to have some mains of pointing to
data objects in the heap.  See for example, 'Crafting a Compiler', Fischer
et al, 2010, pp.500-511.  Here, what amounts to relocatable blocks in the
heap, are manipulated especially for garbage collection and compaction (with
special reference the problems encountered in C).  You will note the use of
'global pointers' to reference data objects there.

Ian  

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

#25417

IMO, this is the sort of thing that would be excellent to include as a utility library on the FLAG website:

http://soton.mpeforth.com/flag/

Though I think it's a bit on the heavy side for inclusion into the standard. I do believe that dynamic memory management is very useful, but I would err against including it in the standard. As an optional extension to the standard? Sure.

[toc] | [prev] | [standalone]

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

csiph-web