Convert an address range into an array

Convert an address range into an array

[Markus Kuhn]

Problem: I have memory-mapped a file into my address space using
mmap(). I have parsed data structures in this file and I have located
a continuous string of characters in the address range A to B.
I now want to convert this address range into an Ada String type,
which I can then pass on to a procedure that expects a String
parameter. I do NOT want to copy the (potentially very large)
sequence of bytes for performance reasons.

Basically, I want to get somehow a value

  S : String;

such that

  S(S'First)'Access = A 
  S(S'Last)'Access = B
  S'First = 1

which I can then pass on to a prodecure without copying the bytes.
All I want to allocate is the (First,Last) meta-data of the array,
not the array data itself. In other words, I want to combine the
efficiency of C's pointer+length representation of memory chunks
with the comfort and safety of Ada's arrays, but none of the
textbooks explain how to do this.

What is the proper Ada way of turning a variable address range
into an array located there? Representation clauses? Or should the
efficient zero-copying handling of memory mapped files, packet
headers, etc. better be done via good old pointer arithmetic
like in C?

The compiler is GNAT on Linux, but the most portable solution
would be preferred.

Markus

-- 
Markus G. Kuhn, Computer Laboratory, University of Cambridge, UK
Email: mkuhn at acm.org,  WWW: <http://www.cl.cam.ac.uk/~mgk25/>

Re: Convert an address range into an array

[Robert Dewar]

In article <7jdjov$21$1@pegasus.csx.cam.ac.uk>,
  mgk25@cl.cam.ac.uk (Markus Kuhn) wrote:

>Basically, I want to get somehow a value

> S :  String;

>such that

> S(S'First)'Access = A > S(S'Last)'Access = B >
S'First = 1

>(where A and B are two addressses)

Well we are not going to be able to find a
solution that is *formally* portable for something
like this, but we can certainly find a solution
that is from a pragmatic point of view portable
(between architectures and between compilers).

There are a couple of approaches.  First, let's
try to get a type that retains proper bounds
checking:

First, we want to deal with a constrained array
here.  Unconstrained arrays have bounds stored
in some implementation dependent format and will get
you into trouble.  So let's first define a subtype
that appropriately represents the range

    subtype XString is String (1 .. expr);

  Here expr can be dynamic, there is no problem in
  that.  However, note that we must define this
  subtype in an appropriate scope.  In this
  particular case, expr is something like

    Positive
     (System.Storage_Elements.To_Integer (B) -
      System.Storage_Elements.To_Integer (A) + 1);

  Now we can proceed in several ways

Method 1a.  Simply use an address clause.  This is
exactly a legitimate use of address clauses, so we
simply say

    S : XString;
    for S'Address use A;

  This will likely work on most implementations, assuming that
  they do not use dope vectors or descriptors for constrained
  arrays. This is a reasonable assumption, and certainly true
  of GNAT, but in practice it may be slightly more portable
  to use:

Method 1b.  Use Unchecked_Conversion

  type XString_Ptr is access all XString; function
  To_XString_Ptr is new Unchecked_Conversion
  (Address, XString_Ptr);

    SP :  XString_Ptr := To_String_Ptr (A);

  in practice, this works fine, since all
  implementations will use the same representation
  for constrained pointers and addresses.  Note that
  approach 1b will NOT work if you try to use
  "access string" instead of the
  pointer-to-constrained type, since then bounds get
  involved.

  However, there is no requirement that this work, so a bit
  cleaner, is to use:

Method 1c.  Use Address_To_Access_Conversions

    package XString_Ops is new
    Address_To_Access_Conversions (XString);

    subtype Xstring_Ptr is Xstring_Ops.Object_Pointer;

    SP : XString_Ptr := To_Pointer (A);

  Note:  although the formal of this package has a
  declaration (<>) implying you can use it with an
  unconstrained type such as String, you will get
  into trouble if you try, since we still have the
  bounds problem.

  Basically the issue with "access String" is that
  values of this type have bounds.  Where are these
  bounds stored?  Certainly your memory mapped gizmo
  has no bounds in sight, and even if it did your
  implementation might not have the same idea of how
  to store them.

Here are two rules to follow

  NEVER use unchecked conversion with pointers to
  unconstrained array types

  NEVER use Address_To_Access_Conversions with
  pointers to unconstrained array types.

  Violating these rules is a common cause of
  non-portable code and obscure bugs.  We find this
  coming up frequently in our work helping customers
  to port legacy Ada 83 code.

OK, those approaches work fine, but now for one
other approach that is a little more general and
flexible, but does not retain bounds checking.

  Define a type

  subtype Big_String is String (Positive); type
  Big_String_Ptr is access Big_String;

  This type acts very much like char* in C in that
  it is a pointer that can be used to access
  arbitrary sized character arrays.

Method 2b.  Like 1b but use Big_String_Ptr

Method 2c.  Like 1c but use Big_String_Ptr

  The advantage of Method 2b and 2c is that
  Big_String_Ptr can be used arround the place
  freely without worrying about specialized
  definitions of subtypes and their scopes.  This
  approach is also appropriate when you don't know
  the upper bound in advance, but it is computed as
  you go along, or changes as you go along.

  For an example of the use of "Big" arrays of this
  type, see the GNAT.Table package in the GNAT
  library, which uses this approach to get the
  effect of virtual origin addressing for arrays.

Method 3. Pointer Arithmetic

  Finally, yes, you could use address arithmetic
  (good old pointer arithmetic), and indeed Ada has
  much more flexible pointer arithmetic than C (in
  Ada, unlike C, you can do arbitrary address
  arithmetic, e.g.  compare any two addresses, in a
  portable manner).  However, this is much lower
  level and will kludge up your code unnecessarily.

Ada 83 notes.

  In Ada 83, method 1a is a bit more dubious, it may be
  erroneous, but in practice if the addressed area is not
  otherwise aliased, it should work fine. Method 1b is
  certainly safe (same comments apply to 2a and 2b). Method
  1c, probably the preferable approach for Ada 95 is of course
  not available in Ada 83.

Robert Dewar
Ada Core Technologies

P.S. It is quite true that this sort of thing is not
very well documented in the Ada literature. We find
that issues like this now account for a
substantial part of the support work we provide
for our customers. Choosing the right way to solve
problems like this is critical, and you often find
a lot of bad advice on how to proceed, contaminated
with a lack of clear knowledge on what is and what
is not likely to be implementation dependent.

This is the sort of place where programmers need to
be aware of what they are doing at a low level as
well as a high level. As I noted in previous posts,
this is often missing knowledge.

Thanks, Marcus for an instructive question :-)


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: Convert an address range into an array

[David C. Hoos, Sr.]

Markus Kuhn <mgk25@cl.cam.ac.uk> wrote in message
news:7jdjov$21$1@pegasus.csx.cam.ac.uk...
> Problem: I have memory-mapped a file into my address space using
> mmap(). I have parsed data structures in this file and I have located
> a continuous string of characters in the address range A to B.
> I now want to convert this address range into an Ada String type,
> which I can then pass on to a procedure that expects a String
> parameter. I do NOT want to copy the (potentially very large)
> sequence of bytes for performance reasons.
>
> Basically, I want to get somehow a value
>
>   S : String;
>
> such that
>
>   S(S'First)'Access = A
>   S(S'Last)'Access = B
>   S'First = 1
>
First, this would be a violation of Ada's strong type model, because
you are asking access values to be equal to addresses.

> which I can then pass on to a prodecure without copying the bytes.
> All I want to allocate is the (First,Last) meta-data of the array,
> not the array data itself. In other words, I want to combine the
> efficiency of C's pointer+length representation of memory chunks
> with the comfort and safety of Ada's arrays, but none of the
> textbooks explain how to do this.
>
> What is the proper Ada way of turning a variable address range
> into an array located there? Representation clauses? Or should the
> efficient zero-copying handling of memory mapped files, packet
> headers, etc. better be done via good old pointer arithmetic
> like in C?
>
> The compiler is GNAT on Linux, but the most portable solution
> would be preferred.
>
My solution would be the code which is at the end of this message.
Although the code would not be guaranteed (by the RM) to have
pass-by-reference semantics, examination of the assembly code
generated by GNAT does, and I would suspect that other compilers
would, too, given the nature of strings.

-- begin source code --
with Ada.Text_IO;
with System.Storage_Elements;
procedure Kuhn is
   type String_Access is access all String;
   Start_Address : System.Address;
   End_Address   : System.Address;
   procedure Show_String (The_String : String) is
   begin
      Ada.Text_IO.Put_Line (The_String);
   end Show_String;
   The_String : String :=
     "junk The quick brown fox jumps over the lazy dog's back. junk";
begin
   Start_Address := The_String (5)'Address;
   End_Address := The_String(The_String'Last - 5)'Address;
   declare
      use type System.Storage_Elements.Storage_Count;
      String_Length : Natural :=
        Natural (End_Address - Start_Address + 1);
      The_String : String (1 .. String_Length);
      for The_String'Address use Start_Address;
   begin
      Show_String (The_String);
   end;
end Kuhn;
-- end source code --

Re: Convert an address range into an array

[Matthew Heaney]

mgk25@cl.cam.ac.uk (Markus Kuhn) writes:

> Problem: I have memory-mapped a file into my address space using
> mmap(). I have parsed data structures in this file and I have located
> a continuous string of characters in the address range A to B.
> I now want to convert this address range into an Ada String type,
> which I can then pass on to a procedure that expects a String
> parameter. I do NOT want to copy the (potentially very large)
> sequence of bytes for performance reasons.
> 
> Basically, I want to get somehow a value
> 
>   S : String;
> 
> such that
> 
>   S(S'First)'Access = A 
>   S(S'Last)'Access = B
>   S'First = 1
> 
> which I can then pass on to a prodecure without copying the bytes.
> All I want to allocate is the (First,Last) meta-data of the array,
> not the array data itself. In other words, I want to combine the
> efficiency of C's pointer+length representation of memory chunks
> with the comfort and safety of Ada's arrays, but none of the
> textbooks explain how to do this.
> 
> What is the proper Ada way of turning a variable address range
> into an array located there? Representation clauses? Or should the
> efficient zero-copying handling of memory mapped files, packet
> headers, etc. better be done via good old pointer arithmetic
> like in C?
> 
> The compiler is GNAT on Linux, but the most portable solution
> would be preferred.


How about:

declare

  Length : constant Storage_Offset := B - A + 1;

  S : String (1 .. Length);

  for S'Address use A;

begin

  Op (S);

end;

Won't this work?