[bug #12621] Error while linking laden: "undefined reference to `__chk_fail'"

Update of bug #12621 (project hurd):

                  Status:                    None => Invalid                
             Open/Closed:                    Open => Closed                 

    _______________________________________________________

Follow-up Comment #2:

This is no longer an issue.

    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?12621>

_______________________________________________
  Nachricht geschickt von/durch Savannah
  http://savannah.gnu.org/

How to determine if the button is pressed or not in L4 Dope?

Scheduling Memory in Viengoos

In this note, I very briefly describe how memory is scheduled in
Viengoos and how the per-principal availability metric is calculated.

Principals (called activities) on Viengoos form a hierarchy.  A parent
is able to set the scheduling policy for its immediate children.  When
an activity allocates memory, it is allocated out of its parent's
allocation.

                     o
                10  / \  20
                   o   o

One scheduling parameter is weight.  In the above figure, an activity
has two children, one with weight 10, the other with weight 20.  This
means that the former's share is 1/3 (= 10/(10+20)) of the parent's
allocation, and the latter's share is 2/3s (= 20/(10+20)).

As long as there is memory available, memory allocations are granted.
That is, the Viengoos scheduler is work conserving.  When this is no
longer the case, Viengoos must decide which activity must yield
memory.  This is accomplished by walking the activity hierarchy
starting at the root to find the activity that most exceeds its share
according to its scheduling parameters.  (As nodes as well as leaves
can allocate memory, each activity actually has two scheduling
policies: a child relative policy and a sibling relative policy.  The
sibling relative policy may only be set by the activity controller.
The child relative can be set by the activity itself and controls when
locally allocated resources should be less preferred than child
allocated resources.)

For example, assume there is 100MB RAM available to the parent.  In
this case, the former's share is 33MB and the latter's 67MB.  If the
first child has allocated 40 and the second 60, the the first child
will be chosen to release some memory.

Viengoos also provides a per-principal notion of availability.  The
very short version of how this is calculated is:

  A.available = MAX (A.share, A.allocated * A.pressure)

The share is derived from the scheduling policy and the amount
allocated is exactly that: the amount currently allocated.  When an
activity is selected to revoke pages, its pressure is increased.  The
result is that the available memory decreases.

Continuing with the above example, the first child's share is 40MB and
the second's 67.  Assume that we revoke 5MB from the first child.
This means that its allocation is now 35MB and its pressure has
increase.  When we report the availability to the child, we will not
report 35, but perhaps 34 so as to encourage it to free a bit more
memory.

Availability, along with some other statistics, is regenerated for
each active activity about every 2 seconds.  A thread can wait for
these statistics and when they are made available, it is notified.
This removes the need for polling.

Re: Scheduling Memory in Viengoos

Hi,

First of all, thanks Neal for this info.  It's nice to hear something
about the state of things.

On Thu, Jun 26, 2008 at 12:59:08PM +0200, Neal H. Walfield wrote:
> Principals (called activities)

So they are synonymous?  Why do you have two words for this concept?

> As long as there is memory available, memory allocations are granted.

I understand from your explanation that any activity can reserve some
memory, and it can claim as much memory as it likes, as long as it is
available.  Then when memory is exhausted, some activity's memory will
be shrunk, but never further than the reserved amount.  Is that correct?

Does an activity for which the allocation is shrunk get a notification
and can it somehow save the contents?  Or should every page which is not
reserved be considered cache which can disappear without notice?

> When this is no longer the case, Viengoos must decide which activity
> must yield memory.  This is accomplished by walking the activity
> hierarchy starting at the root to find the activity that most exceeds
> its share according to its scheduling parameters.

Can activities create children without limits?  In that case, this
tree-walking does not have an upper limit on its completion time?

> (As nodes as well as leaves
> can allocate memory, each activity actually has two scheduling
> policies: a child relative policy and a sibling relative policy.  The
> sibling relative policy may only be set by the activity controller.

Which is usually the parent node?

Is child memory available to the parents (direct and indirect)?

> When we report the availability to the child, we will not report 35,
> but perhaps 34 so as to encourage it to free a bit more memory.

A well behaving child would gladly do this, while a badly behaving child
wouldn't do it anyway, right?  Why then not just give real numbers (35)
and let the child be nice explicitly?

> Availability, along with some other statistics, is regenerated for
> each active activity about every 2 seconds.  A thread can wait for
> these statistics and when they are made available, it is notified.
>
> This removes the need for polling.

That is always good. 

Thanks,
Bas

--

-- 
I encourage people to send encrypted e-mail (see http://www.gnupg.org).
If you have problems reading my e-mail, use a better reader.
Please send the central message of e-mails as plain text
   in the message body, not as HTML and definitely not as MS Word.
Please do not use the MS Word format for attachments either.
For more information, see http://pcbcn10.phys.rug.nl/e-mail.html

Some initial results

I've ported the Boehm Garbage Collector to Viengoos.  This was quite
straightforward: it basically compiled and worked straight out of the
box once the required functionality was implemented.  (For the
interested: Unix signals, mmap, munmap and mprotect.  However, this is
already for an advanced configuration and it can work with less.)

I then modified the collection scheduler to take advantage of
Viengoos's availability feature so as to reduce the GC overhead.  The
basic idea is to only perform a collection when the amount of memory
approximates the available memory.

Because the amount of available memory may decrease, we need a way to
release memory to the operating system.  The Boehm GC already provides
basic support for this: after a collection completes, it munmaps
chunks that have not been recently used.  I improved it a bit, the
details are not relevant for this discussion.

The scheduler functions as follows:

  if (allocated_memory < 15/16 * available
      && used_memory < 2/3 * allocated_memory)
    try_to_unmap ()

  if (allocated_memory < 15/16 * available)
    perform_gc ()
    try_to_unmap ()

allocated_memory is the amount of memory allocated from the system.
used_memory is the amount of memory the collector has given out.
try_to_unmap tries to unmap enough memory such that the amount of
allocated memory is below 7/8s the available memory.

To determine the effectiveness of this, I ran a few experiments based
on this benchmark:

  http://www.hpl.hp.com/personal/Hans_Boehm/gc/gc_bench/GCBench.c

The basic idea is that it builds trees, frees and repeats.  I modified
the benchmark to loop 100 times.  I ran the the benchmark on Viengoos
and GNU Linux (on a AMD Duron 1.2Ghz with 512MB, 100MB was provided to
reserved for Pistachio) with the default scheduler and the Viengoos
scheduler.  On GNU Linux, I approximated the Viengoos scheduler by
fixing the availability a priori.  I also ran the tests on Viengoos
again with a memory hog.  The memory hog starts after about one
minute, allocates and writes to 2.5MB of memory per second.  After
allocating half the memory, it sleeps for a minute and then releases
the memory at 2.5MB per second.  The scheduler adapts quite well and
there is little overhead.  The results are shows in this graph:

  http://walfield.org/gcbench/gcbench-progress.png

The summary is:

                          Time (s/rel)  # Collections  Overhead (s)

GNU Linux/Fixed/No Hog      216  1           89            15
Viengoos/Viengoos/No Hog    342  1.58       108            45
Viengoos/Viengoos/Hog       360  1.66       193            51
GNU Linux/Boehm/No Hog      408  1.88      9201           213
Viengoos/Boehm/No Hog       448  2.07      9206           235
Viengoos/Boehm/Hog          488  2.25      9204           257

Some observations:

1) The adaptive Viengoos scheduler takes 75% the time of the
   Boehm scheduler.

2) The hog has little impact.  The adaptation can be seen in this
   graph:

  http://walfield.org/gcbench/gcbench-vg-vg-hog.png

3) Linux is damn fast.  In particular, if you look at the first graph,
   you'll see that the Viengoos runs take 40 seconds to complete the
   first iteration (this is also the time it takes to allocate all
   available memory!).  Each subsequent iteration takes about 3
   seconds.  The problem here is the address space construction.

I also colleted some profiling data to see where the slow spots are.
The data is from the run the Viengoos scheduler and without a hog.
Unless otherwise noted, all the measurements start once Viengoos has
control and end just before Viengoos replies.  That is, they exclude
L4 IPC time.

 - 68 (19%) seconds in the page ager
    - 45 seconds (12%) making 1821419 l4_unmap's to get reference bits
 - 17 seconds (4%) to handle 1022431 page faults 
 - 25.7 seconds (7%) discarding objects.  797121 calls.
 - 1.5 seconds (<1%) allocating 89718 objects
 - 0.5 seconds (<1%) executing 88504 cap_copy's

All other object invocations were negligible.

Don't forget that with the exception of the l4_unmap, these numbers do
not include the time to execute the two IPCs.

The initial ramp up time is constructing the address space.  This is
clearly very, very expensive.  The address space is built just like in
EROS: with cappages and inserting capabilities into them.  On a fault,
Viengoos walks the cappages to find the correct object.  During this
time, the process is allocating objects and inserting them into the
address space.  This is all of the object_alloc calls and the cap
copies.  This is still only two seconds.  I'm guessing that a lot of
time is doing IPC.  I will soon try to better measure this.

The second major slow down is the page ager.  The page ager runs 4
times per second and scans about 400MB looking collecting reference
bits.  This latter part takes 12% of the time.  This is even using
l4_unmap's batch mode allowing for the collection of reference bits
associated with 32 fpages.  It seems to me that L4 is just bad a this.

These two results are strong motivation to port Viengoos to native
hardware and to not continue using L4 as a hardware abstraction.

Neal

Re: Scheduling Memory in Viengoos

At Thu, 26 Jun 2008 12:59:08 +0200,
Neal H. Walfield wrote:
> Viengoos also provides a per-principal notion of availability.  The
> very short version of how this is calculated is:
> 
>   A.available = MAX (A.share, A.allocated * A.pressure)

More precise is:

  A.available = MAX (A.share + unused, A.allocated) * A.pressure

(If unused is non-zero then pressure is 1)

on naming

At Thu, 26 Jun 2008 13:32:53 +0200,
Bas Wijnen wrote:
> On Thu, Jun 26, 2008 at 12:59:08PM +0200, Neal H. Walfield wrote:
> > Principals (called activities)
> 
> So they are synonymous?  Why do you have two words for this concept?

The are not the same thing.  An activity has specific semantics in the
context of my system.  If I were to use the same name as the general
concept, this might lead to confusion.  This is why not all operating
systems are named operating system: they are all instances of the idea
operating system but they differ in their realization.

memory management

At Thu, 26 Jun 2008 13:32:53 +0200,
Bas Wijnen wrote:
> > As long as there is memory available, memory allocations are granted.
> 
> I understand from your explanation that any activity can reserve some
> memory, and it can claim as much memory as it likes, as long as it is
> available.  Then when memory is exhausted, some activity's memory will
> be shrunk, but never further than the reserved amount.  Is that correct?
> 
> Does an activity for which the allocation is shrunk get a notification
> and can it somehow save the contents?  Or should every page which is not
> reserved be considered cache which can disappear without notice?

Memory is transparently multiplexed in the usual Unix fashion.  One
key advantage that Viengoos offers is that it is possible to guide the
eviction decision.

A policy can be associated with a frame of memory.  This is done at
access time by copying the policy stored in the capability into the
frame.  The policy that is stored in the capability is saved alongside
the frame.  By not storing the policy in the object but in the
capability, any user of an object can control the management policy of
the associated memory--even read-only users (although they cannot set
the discardable bit).  The policy consists of a priority and a
discardability predicate.

When Viengoos selects a page to evict from an activity, it chooses the
page with the lowest priority.  If there are multiple pages with the
lowest priority, it selects the one that was least recently used.

The discardability predicate allows a program to indicate that the
page can simply be discarded.  When such a frame is choosen for
eviction, it is immediately enqueued on the available list.  When it
is reused, the fact that it was discarded is noted.  The next time the
object is accessed, the accessing thread receives a discarded
activation allowing it to take appropriate action, e.g., regenerating
the content.

When calculating the availability, Viengoos also considers allocation
trends.  If a lot of memory is being allocated and an activity has
more than its fair share, the amount of available memory will be
decreased.  This enables proactive (as opposed to reactive
adaptation).

using activities in a DoS attack vector

At Thu, 26 Jun 2008 13:32:53 +0200,
Bas Wijnen wrote:
> Can activities create children without limits?  In that case, this
> tree-walking does not have an upper limit on its completion time?

An activity is a normal object.  It is not treated much differently
from a page, a cappage, or a thread.  So, to answer your question,
insofar as an activity has memory, it have that many *active*
activities.  That's the key.  Viengoos only calculates statistics for
active activities.  An activity is active if it is in memory, and
activities are subject to the usual paging mechanisms (with the
exception that an activity may only be paged out if its children are
paged out and no object refers to it).

This limits the scope of such an attack to the amount of memory that
is available to an activity.  Nevertheless, generating statistics for
a large number of activities can still require a significant amount of
CPU time.  So far, I have only seriously addressed memory accouting.
Once CPU time is also consider, it makes sense to charge activities
for this service.  If an activity doesn't have any CPU time, neither
does its children.  Thus, we could simply stop recursing when we
encounter such an activity.

Re: Scheduling Memory in Viengoos

At Thu, 26 Jun 2008 13:32:53 +0200,
Bas Wijnen wrote:
> > (As nodes as well as leaves
> > can allocate memory, each activity actually has two scheduling
> > policies: a child relative policy and a sibling relative policy.  The
> > sibling relative policy may only be set by the activity controller.
> 
> Which is usually the parent node?

Yes.

> Is child memory available to the parents (direct and indirect)?

What do you mean?  Are you asking whether a parent can examine the
memory that a child allocates?  The answer is yes, with some pain.  So
far, I haven't needed this functionality, however.