auto import from //depot/cupcake/@132589

7 files changed, 90 insertions, 317 deletions

diff --git a/libc/bionic/pthread-timers.c b/libc/bionic/pthread-timers.c
index 7b9c99e..818b47d 100644
--- a/libc/bionic/pthread-timers.c
+++ b/libc/bionic/pthread-timers.c
@@ -485,19 +485,16 @@ timer_settime( timer_t                   id,
             timer_gettime_internal(timer, ospec );
         }
 
-        /* compute next expiration time. note that if the
-         * new it_interval is 0, we should disarm the timer
-         */
+        /* compute next expiration time */
         expires = spec->it_value;
-        if (!timespec_is_zero(&expires)) {
-            clock_gettime( timer->clock, &now );
-            if (!(flags & TIMER_ABSTIME)) {
-                timespec_add(&expires, &now);
-            } else {
-                if (timespec_cmp(&expires, &now) < 0)
-                    expires = now;
-            }
+        clock_gettime( timer->clock, &now );
+        if (!(flags & TIMER_ABSTIME)) {
+            timespec_add(&expires, &now);
+        } else {
+            if (timespec_cmp(&expires, &now) < 0)
+                expires = now;
         }
+
         timer->expires = expires;
         timer->period  = spec->it_interval;
         thr_timer_unlock( timer );
diff --git a/linker/Android.mk b/linker/Android.mk
index 48141be..98eceda 100644
--- a/linker/Android.mk
+++ b/linker/Android.mk
@@ -6,8 +6,7 @@ LOCAL_SRC_FILES:= \
 	linker.c \
 	rt.c \
 	dlfcn.c \
-	debugger.c \
-	ba.c
+	debugger.c
 
 LINKER_TEXT_BASE := 0xB0000100
 
@@ -17,9 +16,7 @@ LINKER_AREA_SIZE := 0x01000000
 
 LOCAL_LDFLAGS := -Wl,-Ttext,$(LINKER_TEXT_BASE)
 
-LOCAL_CFLAGS += -DPRELINK
-LOCAL_CFLAGS += -DLINKER_TEXT_BASE=$(LINKER_TEXT_BASE)
-LOCAL_CFLAGS += -DLINKER_AREA_SIZE=$(LINKER_AREA_SIZE)
+LOCAL_CFLAGS += -DPRELINK -DLINKER_TEXT_BASE=$(LINKER_TEXT_BASE) -DLINKER_AREA_SIZE=$(LINKER_AREA_SIZE)
 
 # we need to access the Bionic private header <bionic_tls.h>
 # in the linker
diff --git a/linker/ba.c b/linker/ba.c
deleted file mode 100644
index bea6f84..0000000
--- a/linker/ba.c
+++ /dev/null
@@ -1,180 +0,0 @@
-/*
- * Copyright (C) 2008 The Android Open Source Project
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *  * Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- *  * Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in
- *    the documentation and/or other materials provided with the
- *    distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
- * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
- * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
- * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
- * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
- * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
- * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
- * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#include "linker.h"
-#include "linker_debug.h"
-#include "ba.h"
-
-struct ba_bits {
-    unsigned allocated:1;           /* 1 if allocated, 0 if free */
-    unsigned order:7;               /* size of the region in ba space */
-};
-
-struct ba_info {
-    /* start address of the ba space */
-    unsigned long base;
-    /* total size of the ba space */
-    unsigned long size;
-    /* number of entries in the ba space */
-    int num_entries;
-    /* the bitmap for the region indicating which entries are allocated
-     * and which are free */
-    struct ba_bits *bitmap;
-};
-
-#undef min
-#define min(a,b) ((a)<(b)?(a):(b))
-
-#define BA_MIN_ALLOC LIBINC
-#define BA_MAX_ORDER 128
-#define BA_START LIBBASE
-#define BA_SIZE (LIBLAST - LIBBASE)
-
-#define BA_IS_FREE(index) (!(ba.bitmap[index].allocated))
-#define BA_ORDER(index) ba.bitmap[index].order
-#define BA_BUDDY_INDEX(index) ((index) ^ (1 << BA_ORDER(index)))
-#define BA_NEXT_INDEX(index) ((index) + (1 << BA_ORDER(index)))
-#define BA_OFFSET(index) ((index) * BA_MIN_ALLOC)
-#define BA_START_ADDR(index) (BA_OFFSET(index) + ba.base)
-#define BA_LEN(index) ((1 << BA_ORDER(index)) * BA_MIN_ALLOC)
-
-static struct ba_bits ba_bitmap[BA_SIZE / BA_MIN_ALLOC];
-
-static struct ba_info ba = {
-    .base = BA_START,
-    .size = BA_SIZE,
-    .bitmap = ba_bitmap,
-    .num_entries = sizeof(ba_bitmap)/sizeof(ba_bitmap[0]),
-};
-
-void ba_init(void)
-{
-    int i, index = 0;
-    for (i = sizeof(ba.num_entries) * 8 - 1; i >= 0; i--) {
-        if (ba.num_entries &  1<<i) {
-            BA_ORDER(index) = i;
-            index = BA_NEXT_INDEX(index);
-        }
-    }
-}
-
-int ba_free(int index)
-{
-    int buddy, curr = index;
-
-    /* clean up the bitmap, merging any buddies */
-    ba.bitmap[curr].allocated = 0;
-    /* find a slots buddy Buddy# = Slot# ^ (1 << order)
-     * if the buddy is also free merge them
-     * repeat until the buddy is not free or end of the bitmap is reached
-     */
-    do {
-        buddy = BA_BUDDY_INDEX(curr);
-        if (BA_IS_FREE(buddy) &&
-                BA_ORDER(buddy) == BA_ORDER(curr)) {
-            BA_ORDER(buddy)++;
-            BA_ORDER(curr)++;
-            curr = min(buddy, curr);
-        } else {
-            break;
-        }
-    } while (curr < ba.num_entries);
-
-    return 0;
-}
-
-static unsigned long ba_order(unsigned long len)
-{
-    unsigned long i;
-
-    len = (len + BA_MIN_ALLOC - 1) / BA_MIN_ALLOC;
-    len--;
-    for (i = 0; i < sizeof(len)*8; i++)
-        if (len >> i == 0)
-            break;
-    return i;
-}
-
-int ba_allocate(unsigned long len)
-{
-    int curr = 0;
-    int end = ba.num_entries;
-    int best_fit = -1;
-    unsigned long order = ba_order(len);
-
-    if (order > BA_MAX_ORDER)
-        return -1;
-
-    /* look through the bitmap:
-     *  if you find a free slot of the correct order use it
-     *  otherwise, use the best fit (smallest with size > order) slot
-     */
-    while (curr < end) {
-        if (BA_IS_FREE(curr)) {
-            if (BA_ORDER(curr) == (unsigned char)order) {
-                /* set the not free bit and clear others */
-                best_fit = curr;
-                break;
-            }
-            if (BA_ORDER(curr) > (unsigned char)order &&
-                (best_fit < 0 ||
-                 BA_ORDER(curr) < BA_ORDER(best_fit)))
-                best_fit = curr;
-        }
-        curr = BA_NEXT_INDEX(curr);
-    }
-
-    /* if best_fit < 0, there are no suitable slots,
-     * return an error
-     */
-    if (best_fit < 0)
-        return -1;
-
-    /* now partition the best fit:
-     *  split the slot into 2 buddies of order - 1
-     *  repeat until the slot is of the correct order
-     */
-    while (BA_ORDER(best_fit) > (unsigned char)order) {
-        int buddy;
-        BA_ORDER(best_fit) -= 1;
-        buddy = BA_BUDDY_INDEX(best_fit);
-        BA_ORDER(buddy) = BA_ORDER(best_fit);
-    }
-    ba.bitmap[best_fit].allocated = 1;
-    return best_fit;
-}
-
-unsigned long ba_start_addr(int index)
-{
-    return BA_START_ADDR(index);
-}
-
-unsigned long ba_len(int index)
-{
-    return BA_LEN(index);
-}
diff --git a/linker/ba.h b/linker/ba.h
deleted file mode 100644
index 78f4626..0000000
--- a/linker/ba.h
+++ /dev/null
@@ -1,38 +0,0 @@
-/*
- * Copyright (C) 2008 The Android Open Source Project
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *  * Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- *  * Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in
- *    the documentation and/or other materials provided with the
- *    distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
- * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
- * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
- * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
- * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
- * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
- * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
- * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-#ifndef __LINKER_BA_H
-#define __LINKER_BA_H
-
-extern void ba_init(void);
-extern int ba_allocate(unsigned long len);
-extern int ba_free(int index);
-extern unsigned long ba_start_addr(int index);
-extern unsigned long ba_len(int index);
-
-#endif
diff --git a/linker/linker.c b/linker/linker.c
index 91435de..7b19835 100644
--- a/linker/linker.c
+++ b/linker/linker.c
@@ -49,8 +49,6 @@
 #include "linker.h"
 #include "linker_debug.h"
 
-#include "ba.h"
-
 #define SO_MAX 64
 
 /* >>> IMPORTANT NOTE - READ ME BEFORE MODIFYING <<<
@@ -112,8 +110,7 @@ extern void __attribute__((noinline)) rtld_db_dlactivity(void);
 
 extern void  sched_yield(void);
 
-static struct r_debug _r_debug = {1, NULL, &rtld_db_dlactivity,
-                                  RT_CONSISTENT, 0};
+static struct r_debug _r_debug = {1, NULL, &rtld_db_dlactivity, RT_CONSISTENT, 0};
 static struct link_map *r_debug_tail = 0;
 
 //static pthread_mutex_t _r_debug_lock = PTHREAD_MUTEX_INITIALIZER;
@@ -210,7 +207,6 @@ static soinfo *alloc_info(const char *name)
     memset(si, 0, sizeof(soinfo));
     strcpy((char*) si->name, name);
     sonext->next = si;
-    si->ba_index = -1; /* by default, prelinked */
     si->next = NULL;
     si->refcount = 0;
     sonext = si;
@@ -482,6 +478,8 @@ static int open_library(const char *name)
     return -1;
 }
 
+static unsigned libbase = LIBBASE;
+
 /* temporary space for holding the first page of the shared lib
  * which contains the elf header (with the pht). */
 static unsigned char __header[PAGE_SIZE];
@@ -627,67 +625,64 @@ get_lib_extents(int fd, const char *name, void *__hdr, unsigned *total_sz)
  *     segments into the correct locations within this memory range.
  *
  * Args:
- *     si->base: The requested base of the allocation. If 0, a sane one will be
+ *     req_base: The requested base of the allocation. If 0, a sane one will be
  *               chosen in the range LIBBASE <= base < LIBLAST.
- *     si->size: The size of the allocation.
+ *     sz: The size of the allocation.
  *
  * Returns:
- *     -1 on failure, and 0 on success.  On success, si->base will contain
- *     the virtual address at which the library will be mapped.
+ *     NULL on failure, and non-NULL pointer to memory region on success.
  */
-
-static int reserve_mem_region(soinfo *si)
+static void *
+alloc_mem_region(const char *name, unsigned req_base, unsigned sz)
 {
-    void *base = mmap((void *)si->base, si->size, PROT_READ | PROT_EXEC,
-                      MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
-    if (base == MAP_FAILED) {
-        ERROR("%5d can NOT map (%sprelinked) library '%s' at 0x%08x "
-              "as requested, will try general pool: %d (%s)\n",
-              pid, (si->base ? "" : "non-"), si->name, si->base,
-              errno, strerror(errno));
-        return -1;
-    } else if (base != (void *)si->base) {
-        ERROR("OOPS: %5d %sprelinked library '%s' mapped at 0x%08x, "
-              "not at 0x%08x\n", pid, (si->base ? "" : "non-"),
-              si->name, (unsigned)base, si->base);
-        munmap(base, si->size);
-        return -1;
-    }
-    return 0;
-}
+    void *base;
+
+    if (req_base) {
+        /* we should probably map it as PROT_NONE, but the init code needs
+         * to read the phdr, so mark everything as readable. */
+        base = mmap((void *)req_base, sz, PROT_READ | PROT_EXEC,
+                    MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+        if (base == MAP_FAILED) {
+            WARN("%5d can NOT map (prelinked) library '%s' at 0x%08x "
+                 "as requested, will try general pool: %d (%s)\n",
+                 pid, name, req_base, errno, strerror(errno));
+        } else if (base != (void *)req_base) {
+            ERROR("OOPS: %5d prelinked library '%s' mapped at 0x%08x, "
+                  "not at 0x%08x\n", pid, name, (unsigned)base, req_base);
+            munmap(base, sz);
+            return NULL;
+        }
 
-static int
-alloc_mem_region(soinfo *si)
-{
-    if (si->base) {
-        /* Attempt to mmap a prelinked library. */
-        si->ba_index = -1;
-        return reserve_mem_region(si);
+        /* Here we know that we got a valid allocation. Hooray! */
+        return base;
     }
 
-    /* This is not a prelinked library, so we attempt to allocate space
-       for it from the buddy allocator, which manages the area between
-       LIBBASE and LIBLAST.
-    */
-    si->ba_index = ba_allocate(si->size);
-    if(si->ba_index >= 0) {
-        si->base = ba_start_addr(si->ba_index);
-        PRINT("%5d mapping library '%s' at %08x (index %d) " \
-              "through buddy allocator.\n",
-              pid, si->name, si->base, si->ba_index);
-        if (reserve_mem_region(si) < 0) {
-            ba_free(si->ba_index);
-            si->ba_index = -1;
-            si->base = 0;
-            goto err;
+    /* We either did not request a specific base address to map at
+     * (i.e. not-prelinked) OR we could not map at the requested address.
+     * Try to find a memory range in our "reserved" area that can be mapped.
+     */
+    while(libbase < LIBLAST) {
+        base = mmap((void*) libbase, sz, PROT_READ | PROT_EXEC,
+                    MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+
+        if(((unsigned)base) == libbase) {
+            /* success -- got the address we wanted */
+            return base;
         }
-        return 0;
+
+        /* If we got a different address than requested (rather than
+         * just a failure), we need to unmap the mismapped library
+         * before trying again
+         */
+        if(base != MAP_FAILED)
+            munmap(base, sz);
+
+        libbase += LIBINC;
     }
 
-err:
     ERROR("OOPS: %5d cannot map library '%s'. no vspace available.\n",
-          pid, si->name);
-    return -1;
+          pid, name);
+    return NULL;
 }
 
 #define MAYBE_MAP_FLAG(x,from,to)    (((x) & (from)) ? (to) : 0)
@@ -917,7 +912,8 @@ load_library(const char *name)
     int cnt;
     unsigned ext_sz;
     unsigned req_base;
-    soinfo *si = NULL;
+    void *base;
+    soinfo *si;
     Elf32_Ehdr *hdr;
 
     if(fd == -1)
@@ -943,6 +939,14 @@ load_library(const char *name)
     TRACE("[ %5d - '%s' (%s) wants base=0x%08x sz=0x%08x ]\n", pid, name,
           (req_base ? "prelinked" : "not pre-linked"), req_base, ext_sz);
 
+    /* Carve out a chunk of memory where we will map in the individual
+     * segments */
+    base = alloc_mem_region(name, req_base, ext_sz);
+    if (base == NULL)
+        goto fail;
+    TRACE("[ %5d allocated memory for %s @ %p (0x%08x) ]\n",
+          pid, name, base, (unsigned) ext_sz);
+
     /* Now configure the soinfo struct where we'll store all of our data
      * for the ELF object. If the loading fails, we waste the entry, but
      * same thing would happen if we failed during linking. Configuring the
@@ -952,31 +956,19 @@ load_library(const char *name)
     if (si == NULL)
         goto fail;
 
-    /* Carve out a chunk of memory where we will map in the individual
-     * segments */
-    si->base = req_base;
+    si->base = (unsigned)base;
     si->size = ext_sz;
     si->flags = 0;
     si->entry = 0;
     si->dynamic = (unsigned *)-1;
-    if (alloc_mem_region(si) < 0)
-        goto fail;
-
-    TRACE("[ %5d allocated memory for %s @ %p (0x%08x) ]\n",
-          pid, name, (void *)si->base, (unsigned) ext_sz);
 
     /* Now actually load the library's segments into right places in memory */
-    if (load_segments(fd, &__header[0], si) < 0) {
-        if (si->ba_index >= 0) {
-            ba_free(si->ba_index);
-            si->ba_index = -1;
-        }
+    if (load_segments(fd, &__header[0], si) < 0)
         goto fail;
-    }
 
     /* this might not be right. Technically, we don't even need this info
      * once we go through 'load_segments'. */
-    hdr = (Elf32_Ehdr *)si->base;
+    hdr = (Elf32_Ehdr *)base;
     si->phdr = (Elf32_Phdr *)((unsigned char *)si->base + hdr->e_phoff);
     si->phnum = hdr->e_phnum;
     /**/
@@ -985,7 +977,6 @@ load_library(const char *name)
     return si;
 
 fail:
-    if (si) free_info(si);
     close(fd);
     return NULL;
 }
@@ -994,6 +985,8 @@ static soinfo *
 init_library(soinfo *si)
 {
     unsigned wr_offset = 0xffffffff;
+    unsigned libbase_before = 0;
+    unsigned libbase_after = 0;
 
     /* At this point we know that whatever is loaded @ base is a valid ELF
      * shared library whose segments are properly mapped in. */
@@ -1003,10 +996,24 @@ init_library(soinfo *si)
     if (si->base < LIBBASE || si->base >= LIBLAST)
         si->flags |= FLAG_PRELINKED;
 
+        /* Adjust libbase for the size of this library, rounded up to
+        ** LIBINC alignment.  Make note of the previous and current
+        ** value of libbase to allow us to roll back in the event of
+        ** a link failure.
+        */
+    if (!(si->flags & FLAG_PRELINKED)) {
+        libbase_before = libbase;
+        libbase += (si->size + (LIBINC - 1)) & (~(LIBINC - 1));
+        libbase_after = libbase;
+    }
+
     if(link_image(si, wr_offset)) {
             /* We failed to link.  However, we can only restore libbase
             ** if no additional libraries have moved it since we updated it.
             */
+        if(!(si->flags & FLAG_PRELINKED) && (libbase == libbase_after)) {
+            libbase = libbase_before;
+        }
         munmap((void *)si->base, si->size);
         return NULL;
     }
@@ -1060,12 +1067,6 @@ unsigned unload_library(soinfo *si)
         }
 
         munmap((char *)si->base, si->size);
-        if (si->ba_index >= 0) {
-            PRINT("%5d releasing library '%s' address space at %08x "\
-                  "through buddy allocator.\n",
-                  pid, si->name, si->base);
-            ba_free(si->ba_index);
-        }
         free_info(si);
         si->refcount = 0;
     }
@@ -1707,8 +1708,6 @@ unsigned __linker_init(unsigned **elfdata)
         vecs += 2;
     }
 
-    ba_init();
-
     si->base = 0;
     si->dynamic = (unsigned *)-1;
     si->wrprotect_start = 0xffffffff;
diff --git a/linker/linker.h b/linker/linker.h
index d80c761..3ad5104 100644
--- a/linker/linker.h
+++ b/linker/linker.h
@@ -95,8 +95,6 @@ struct soinfo
     unsigned entry;
     unsigned base;
     unsigned size;
-    // buddy-allocator index, negative for prelinked libraries
-    int ba_index;
 
     unsigned *dynamic;
 
diff --git a/linker/linker_debug.h b/linker/linker_debug.h
index 3cc1343..6e396fd 100644
--- a/linker/linker_debug.h
+++ b/linker/linker_debug.h
@@ -35,8 +35,8 @@
  * this on when submitting back to repository */
 #define LINKER_DEBUG         0
 #define TRACE_DEBUG          0
-#define DO_TRACE_LOOKUP      0
-#define DO_TRACE_RELO        0
+#define DO_TRACE_LOOKUP      1
+#define DO_TRACE_RELO        1
 #define TIMING               0
 #define STATS                0
 #define COUNT_PAGES          0