lkml.org 
[lkml]   [2008]   [Mar]   [17]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    Subject[PATCH prototype] [0/8] Predictive bitmaps for ELF executables
    Date

    This patchkit is an experimental optimization I played around with
    some time ago.

    This is more a prototype still, but I wanted to push it out
    so that other people can play with it.

    The basic idea is that most programs have the same working set
    over multiple runs. So instead of demand paging all the text pages
    in the order the program runs save the working set to disk and prefetch
    it at program start and then save it at program exit.

    This allows some optimizations:
    - it can avoid unnecessary disk seeks because the blocks will be fetched in
    sorted offset order instead of program execution order.
    - batch kernel entries (each demand page exception has some
    overhead just for entering the kernel). This keeps the caches hot too.
    - The prefetch could be in theory done in the background while the program
    runs (although that is not implemented currently)

    Some details on the implementation:

    To do all this we need a bitmap space somewhere in the ELF executable. I originally
    hoped to use a standard ELF PHDR for this, which are already parsed by the
    Linux ELF loader. However the problem is that PHDRs are part of the
    mapped program image and inserting any new ones requires relinking
    the program. Since relinking programs just to get this would be
    rather heavy-handed I used a hack by setting another bitflag
    in the gnu_execstack header and when it is set let the kernel
    look for ELF SHDRs at the end of the file. Disadvantage is that
    this costs a seek, but it allows easily to update existing
    executables with a simple too.

    The seek overhead would be gone if the linkers are taught to
    always generate a PBITMAP bitmap header.

    I also considered external bitmap files, but just putting it into the ELF
    files and keeping it all together seemed much nicer policywise.

    Then there is some probability of thrashing the bitmap, e.g. when
    a program runs in different modi with totally different working sets
    (a good example of this would be busybox). I haven't found
    a good heuristic to handle this yet (e.g. one possibility would
    be to or the bitmap instead of rewriting it on exit) this is something
    that could need further experimentation. Also one doesn't want
    too many bitmap updates of course so there is a simple heuristic
    to not update bitmaps more often than a sysctl configurable
    interval.

    User tools:
    ftp://ftp.firstfloor.org/pub/ak/pbitmap/pbitmap.c
    is a simple program to a pbitmap shdrs to an existing ELF executable.

    Base kernel:
    Again 2.6.25-rc6

    Drawbacks:
    - No support for dynamic libraries right now (except very clumpsily
    through the mmap_slurp hack). This is the main reason it is not
    very useful for speed up desktops currently.

    - Executable files have to be writable by the user executing it
    currently to get bitmap updates. It would be possible to let the
    kernel bypass this, but I haven't thought too much about the security
    implications of it.
    However any user can use the bitmap data written by a user with
    write rights.

    That's currently one of the bigger usability issues (together
    with the missing shared library support) and why it is more
    a prototype than a fully usable solution.

    Possible areas of improvements if anybody is interested:
    - Background prefetch
    - Tune all the sysctl defaults
    - Implement shared library support (will require glibc support)
    - Do something about the executable access problem
    - Experiment with more fancy heuristics to update bitmaps (like OR
    or do aging etc.)

    -Andi


    \
     
     \ /
      Last update: 2008-03-18 02:13    [W:0.028 / U:0.280 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site