Validating/using all 2^lgn address bits 
Author Message
 Validating/using all 2^lgn address bits

Quote:

>With respect to using a subfield of the address as a type tag: given a
>sufficiently large sparse address space, you can "just do it" by
>allocating different primitive types in different parts of the address
>space.

This has been done for quite a long time, even on machines with fairly
small address spaces.  The allocation technique is known as BIBOP, for
``Big Bag O' Pages'', and seems to have mostly died out (due in part to
the historical lack of support in Unix for attaching memory to random
chunks of address space).

In general, it seems that systems which use BIBOP like to have a `real'
type tag associated with heap objects as well as a high-bit type.  This
is because 32-bit address spaces don't give you enough high address
bits to play freely with, so you reserve smallish sets of pages for
allocating objects of each type.  Using a pure BIBOP system, you then
have to do a little bit of table lookup before you can determine what
type an object is from its high address bits.

The only current Lispy implementation I know of that uses BIBOP typing
is Chez Scheme from Indiana University (see IU TR 400), which uses it
solely for the storage manager to play with; run-time type
identification for other purposes is done using normal tag bits, being
faster as outlined above.  The claimed win is that BIBOP frobbery makes
it easier for Chez' allocator and collector to accommodate other
languages' run time systems -- the GC can sweep through memory in the
normal fashion, but when it reaches a group of pages marked as
`externally allocated', it just skips past them.  There's also some
cleverness in their BIBOP system that allows their generational GC to
avoid copying large objects, though I can't remember the exact details
of this.

I don't know what the Chez folks make of the possibilities of thrashing
the TLB or cacking on access locality as mentioned by Rob MacLachlan.

        <b

--
Bryan O'Sullivan               u nas est tolko odyeen yagnyonok seychas.

University of Glasgow          web.gunge: http://www.*-*-*.com/ ~bos



Fri, 21 Feb 1997 22:02:55 GMT  
 Validating/using all 2^lgn address bits
[Followups restricted.]

Quote:

>Franz Lisp still exists and is usable with FreeBSD and NetBSD
>and (presumably) other 4.3 (soon to be 4.4) -based systems.

Did it use BIBOP under versions of BSD prior to those that had NFS (and
hence mmap) folded in, do you know?

        <b

--
Bryan O'Sullivan



Sat, 22 Feb 1997 03:32:18 GMT  
 Validating/using all 2^lgn address bits

   >With respect to using a subfield of the address as a type tag: given a
   >sufficiently large sparse address space, you can "just do it" by
   >allocating different primitive types in different parts of the address
   >space.

   This has been done for quite a long time, even on machines with fairly
   small address spaces.  The allocation technique is known as BIBOP, for
   ``Big Bag O' Pages'', and seems to have mostly died out (due in part to
   the historical lack of support in Unix for attaching memory to random
   chunks of address space).

I think you're confused.  I believe that the term BIBOP has generally
been applied to allocation schemes that pack objects of a particular
type on a "page" of storage (not necessarily the same size as the
operating system's virtual memory pages).  When the current page of,
say, list space or double-float space is used up, you go allocate a
new one, but this allocation may be done adjacent to the existing
heap memory.  The high-order bits of a pointer tell you what page
you're on, but they don't directly encode the type of object on that
page -- you need a table-lookup to do that.

I first saw this technique used in a version of Maclisp developed by
Jonl White back in the 1970's, but I don't know if he coined the term
"BIBOP".  I think that Franz used BIBOP in this sense.

The scheme of using some of the high-order address bits to directly
encode the type is a different idea (and doesn't have a snappy names
as far as I know).  In this scheme, each type is kept in a contiguous
chunk of the address space, and these chunks are separated by many
megabytes of unused space.  This provides lots of room for each space
to grow, if there aren't too many of them, but it has the problems
that others have pointed out, especially in some older versions of
Unix which insist on allocating memory in one or two contiguous
chunks.

-- Scott

===========================================================================

Principal Research Scientist            Phone:     412 268-2575
School of Computer Science              Fax:       412 268-5576 (new!)
Carnegie Mellon University              Latitude:  40:26:46 N
5000 Forbes Avenue                      Longitude: 79:56:55 W
Pittsburgh, PA 15213                    Mood:      :-)
===========================================================================



Sat, 22 Feb 1997 06:08:24 GMT  
 Validating/using all 2^lgn address bits

Quote:


>>With respect to using a subfield of the address as a type tag: given a
>>sufficiently large sparse address space, you can "just do it" by
>>allocating different primitive types in different parts of the address
>>space.

>This has been done for quite a long time, even on machines with fairly
>small address spaces.  The allocation technique is known as BIBOP, for
>``Big Bag O' Pages'', and seems to have mostly died out (due in part to
>the historical lack of support in Unix for attaching memory to random
>chunks of address space).

Franz Lisp, the BSD Lisp, uses BIBOP.  Some objects also have a header
that includes a type.  (E.g. struct instances.)

Quote:
>The only current Lispy implementation I know of that uses BIBOP typing
>is Chez Scheme from Indiana University [...]

Franz Lisp still exists and is usable with FreeBSD and NetBSD
and (presumably) other 4.3 (soon to be 4.4) -based systems.
It is not strongly restricted as to hardware since I have a
compiler for it that compiles to C.  However, there's still a
small amount of assembly code in the 386 port and some work
would be needed to get it working on incompatible hardware.

(If you want a copy of Franz for 386 BSD systems, I think it's
mentioned in the FAQ these days so I won't repeat the information
here.  Should add it to my WWW page at some point...)

-- jeff



Sat, 22 Feb 1997 01:02:48 GMT  
 Validating/using all 2^lgn address bits

Quote:

>You can just allocate a page [...] and record
>it in a table mapping high-order bits to types.

I've just looked back through the thread and I see that Bryan O'Sullivan
already mentioned this.  Anyway, it's what Franz does.

-- Richard
--

Ooooh!  I didn't know we had a king.  I thought we were an
autonomous collective.



Sat, 22 Feb 1997 20:45:19 GMT  
 Validating/using all 2^lgn address bits

Quote:

>[Followups restricted.]


>>Franz Lisp still exists and is usable with FreeBSD and NetBSD
>>and (presumably) other 4.3 (soon to be 4.4) -based systems.

>Did it use BIBOP under versions of BSD prior to those that had NFS (and
>hence mmap) folded in, do you know?

Franz was in 4.1 BSD, which I'm pretty sure didn't have mmap.
Also, Franz doesn't _use_ mmap even in FreeBSD and NetBSD
(which do have it).

-- jeff



Sun, 23 Feb 1997 07:06:44 GMT  
 Validating/using all 2^lgn address bits

Quote:

>Did it use BIBOP under versions of BSD prior to those that had NFS (and
>hence mmap) folded in, do you know?

Yes.  It doesn't use mmap even now.

You don't need to be able to choose addresses in order to use BIBOP.
You can just allocate a page (not necessarily a VM page; just an area
whose size is a power of two and aligned to the same size) and record
it in a table mapping high-order bits to types.

-- Richard
--

Ooooh!  I didn't know we had a king.  I thought we were an
autonomous collective.



Sat, 22 Feb 1997 20:00:05 GMT  
 Validating/using all 2^lgn address bits

Quote:

>I don't know what the Chez folks make of the possibilities of thrashing
>the TLB or cacking on access locality as mentioned by Rob MacLachlan.

I didn't see the note by Rob MacLachlan, but since Chez Scheme's
segments are contiguous rather than spread throughout virtual memory
these problems do not occur significantly more often than with flat
heap layouts.

R. Kent Dybvig                 | Computer Science Department

812/855-6486                   | Bloomington, IN 47405 USA



Mon, 24 Feb 1997 04:08:29 GMT  
 Validating/using all 2^lgn address bits

Quote:

> Did it use BIBOP under versions of BSD prior to those that had NFS
> (and hence mmap) folded in, do you know?

It sure did.  Franz under 4.1bsd used BIBOP.

It didn't use any OS features to handle page mapping; it just had a big table
indexed by the high order bits of the address, giving the type for each page.

Amanda Walker
InterCon Systems Corporation
(Lisp hacker in a previous life, and still occasionally in my spare time)



Sat, 22 Feb 1997 23:50:26 GMT  
 
 [ 9 post ] 

 Relevant Pages 

1. Validating/using all 2^lgn address bits

2. Validating/using all 2^lgn address bits

3. Validate e-mail address

4. TASM 32 bits ADDRESS ERROR

5. Using regular expressions to validate data

6. Using FTP to get validated compiler list

7. Validating XML-parser using XML Schema?

8. Using PHP to validate XML

9. Validate XML document using TclXML

10. 16 bits vs 32 bits apps

11. 16 bits Version faster than 32 bits ?????

12. Machine Forth vs ANS : 20 bits vs 32 bits

 

 
Powered by phpBB® Forum Software