Re: [Ocaml-reins-devel] Fedora - Several questions

[Richard W.M. J. <rj...@re...>]

On Wed, Sep 03, 2008 at 04:45:31PM -0400, Michael Furr wrote:
> On Wed, 3 Sep 2008, Richard W.M. Jones wrote:
> > (1) Current, first and only version is '0.1a'.  The 'a' is a problem
> > for Fedora because it's ambiguous whether the next version could be
> > '0.1b' or '0.1'.  Ideally it'd be good if the next version was '0.2'
> > and we could just drop these letters altogether :-)  What will the next
> > verison be?
> 
> The very first version was 0.1.  I released 0.1a just hours later to 
> clarify the license.  The next release will be 0.2 and I plan to stick to 
> numeric releases as a general convention.

Thanks for the clarifications.

Reins has in fact just been approved for Fedora, so will be added
within a matter of days.

  https://bugzilla.redhat.com/show_bug.cgi?id=460732

> > (3) I frequently need a structure called a Segment Tree to represent
> > ranges of memory addresses with holes.  (Or rather, I need to
> > represent ranges of memory addresses with holes, and for that I've
> > implemented a Segment Tree).
> 
>        <--- range1 --->             <--- range2 --->
>                                              <--- range3 --->
>    |   |              |             |        |              |        |
>    0  100            200           300      350            450      500
> 
>    Operations:
>    (i) Fast map from address to byte in range at address or hole.
>    (ii) Fast searches.
>    (iii) If a new range overlaps an old one, then it obscures the old
>      range at overlapping addresses.  (This is currently a slow operation
>      because we rebuild the segment tree).
> 
> I don't quite understand the difference between (i) and (ii).  I guess 
> that for (i), you want to be able to map a value to range (e.g., looking 
> up 150 would give "range1")?  For (ii), is this operation meant to test if 
> a range is already present in the tree?

No (ii) is completely different from that.  The purpose of using the
structure is so that we can search for binary strings within the
memory map, and we need to do this very rapidly, because kernel images
are very large.  So we offer some search primitives that allow you to
quickly look for fixed binary strings within ranges, skipping holes.

> I don't have any experience working with segment trees, but after just 
> reading the article on wikipedia, there appear to be some techniques that 
> help with (iii).  In particular, adding new intervals can be done in O(log 
> N) time where you seem to imply yours is O(n)?  (And in fact, augmented 
> segment trees seem pretty straightforward to implement).

The overlapping case isn't actually that important.  We don't use this
case in practice, although my implementation mostly does the right
thing.

However it turns out that adding new ranges is much more common than I
initially expected, and at the moment my implementation rebuilds the
segment tree from scratch each time, which isn't good.  Again in
practice this doesn't seem to matter that much since the time is
dominated by searches, not by rebuilding the segment tree.  But in a
general purpose structure it'd be nice if we didn't have to completely
rebuild it each time.

> > (a) Over-complex yet rather inflexible.
> 
> I didn't look at your code too deeply, so I don't fully understand what 
> you are referring to (given the coupling of the underlying segment tree vs 
> the memory map that you implemented on top of it), but it seems like it is 
> a good start.  For example, the effectful phantom types don't seem 
> necessary for the underlying data structure, but are used to guard 
> accesses to the underlying data?

Yes, it's all a bit mixed up.

> > (b) Needs to work with an unsigned int64 range, but currently the
> >   range is signed so it breaks with addresses > 0x7fffffff_ffffffff.
> 
> Most of the data structures in Reins are functors over the underlying 
> datatypes used in the containers, so it would be nice to be able to follow 
> this convention.  I don't know what tradeoffs there would be, but 
> supporting intervals over any (totally ordered) data would be great. 
> However, if this is too impractical, Reins also includes the Integral 
> module signature (used by Int, Int32, Int64, etc...) which support 
> arithmetic operations which could be another option.
> 
> > So, any comments on whether I can either reimplement this in terms of
> > another Reins structure, or if a properly functorized segment tree is
> > a good candidate for inclusion in Reins?
> 
> I would love to include a functorized version of your segment tree 
> implementation in the library.  It would be nice if it included the same 
> operations as the other containers (iter, fold, union, compare, to_string, 
> gen, etc..), but if you supplied a core implementation I could certainly 
> help with the implementation of this auxiliary functions.

I'll have a look at doing it, but probably not soon.

Rich.

-- 
Richard Jones, Emerging Technologies, Red Hat  http://et.redhat.com/~rjones
virt-top is 'top' for virtual machines.  Tiny program with many
powerful monitoring features, net stats, disk stats, logging, etc.
http://et.redhat.com/~rjones/virt-top