auto import from //depot/cupcake/@137055

6 files changed, 306 insertions, 82 deletions

diff --git a/linker/Android.mk b/linker/Android.mk
index 98eceda..48141be 100644
--- a/linker/Android.mk
+++ b/linker/Android.mk
@@ -6,7 +6,8 @@ LOCAL_SRC_FILES:= \
 	linker.c \
 	rt.c \
 	dlfcn.c \
-	debugger.c
+	debugger.c \
+	ba.c
 
 LINKER_TEXT_BASE := 0xB0000100
 
@@ -16,7 +17,9 @@ LINKER_AREA_SIZE := 0x01000000
 
 LOCAL_LDFLAGS := -Wl,-Ttext,$(LINKER_TEXT_BASE)
 
-LOCAL_CFLAGS += -DPRELINK -DLINKER_TEXT_BASE=$(LINKER_TEXT_BASE) -DLINKER_AREA_SIZE=$(LINKER_AREA_SIZE)
+LOCAL_CFLAGS += -DPRELINK
+LOCAL_CFLAGS += -DLINKER_TEXT_BASE=$(LINKER_TEXT_BASE)
+LOCAL_CFLAGS += -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
new file mode 100644
index 0000000..bea6f84
--- /dev/null
+++ b/linker/ba.c
@@ -0,0 +1,180 @@
+/*
+ * 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
new file mode 100644
index 0000000..78f4626
--- /dev/null
+++ b/linker/ba.h
@@ -0,0 +1,38 @@
+/*
+ * 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 7b19835..91435de 100644
--- a/linker/linker.c
+++ b/linker/linker.c
@@ -49,6 +49,8 @@
 #include "linker.h"
 #include "linker_debug.h"
 
+#include "ba.h"
+
 #define SO_MAX 64
 
 /* >>> IMPORTANT NOTE - READ ME BEFORE MODIFYING <<<
@@ -110,7 +112,8 @@ 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;
@@ -207,6 +210,7 @@ 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;
@@ -478,8 +482,6 @@ 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];
@@ -625,64 +627,67 @@ get_lib_extents(int fd, const char *name, void *__hdr, unsigned *total_sz)
  *     segments into the correct locations within this memory range.
  *
  * Args:
- *     req_base: The requested base of the allocation. If 0, a sane one will be
+ *     si->base: The requested base of the allocation. If 0, a sane one will be
  *               chosen in the range LIBBASE <= base < LIBLAST.
- *     sz: The size of the allocation.
+ *     si->size: The size of the allocation.
  *
  * Returns:
- *     NULL on failure, and non-NULL pointer to memory region on success.
+ *     -1 on failure, and 0 on success.  On success, si->base will contain
+ *     the virtual address at which the library will be mapped.
  */
-static void *
-alloc_mem_region(const char *name, unsigned req_base, unsigned sz)
-{
-    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;
-        }
 
-        /* Here we know that we got a valid allocation. Hooray! */
-        return base;
+static int reserve_mem_region(soinfo *si)
+{
+    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;
+}
 
-    /* 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);
+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);
+    }
 
-        if(((unsigned)base) == libbase) {
-            /* success -- got the address we wanted */
-            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;
         }
-
-        /* 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;
+        return 0;
     }
 
+err:
     ERROR("OOPS: %5d cannot map library '%s'. no vspace available.\n",
-          pid, name);
-    return NULL;
+          pid, si->name);
+    return -1;
 }
 
 #define MAYBE_MAP_FLAG(x,from,to)    (((x) & (from)) ? (to) : 0)
@@ -912,8 +917,7 @@ load_library(const char *name)
     int cnt;
     unsigned ext_sz;
     unsigned req_base;
-    void *base;
-    soinfo *si;
+    soinfo *si = NULL;
     Elf32_Ehdr *hdr;
 
     if(fd == -1)
@@ -939,14 +943,6 @@ 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
@@ -956,19 +952,31 @@ load_library(const char *name)
     if (si == NULL)
         goto fail;
 
-    si->base = (unsigned)base;
+    /* Carve out a chunk of memory where we will map in the individual
+     * segments */
+    si->base = req_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 (load_segments(fd, &__header[0], si) < 0) {
+        if (si->ba_index >= 0) {
+            ba_free(si->ba_index);
+            si->ba_index = -1;
+        }
         goto fail;
+    }
 
     /* this might not be right. Technically, we don't even need this info
      * once we go through 'load_segments'. */
-    hdr = (Elf32_Ehdr *)base;
+    hdr = (Elf32_Ehdr *)si->base;
     si->phdr = (Elf32_Phdr *)((unsigned char *)si->base + hdr->e_phoff);
     si->phnum = hdr->e_phnum;
     /**/
@@ -977,6 +985,7 @@ load_library(const char *name)
     return si;
 
 fail:
+    if (si) free_info(si);
     close(fd);
     return NULL;
 }
@@ -985,8 +994,6 @@ 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. */
@@ -996,24 +1003,10 @@ 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;
     }
@@ -1067,6 +1060,12 @@ 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;
     }
@@ -1708,6 +1707,8 @@ 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 3ad5104..d80c761 100644
--- a/linker/linker.h
+++ b/linker/linker.h
@@ -95,6 +95,8 @@ 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 6e396fd..3cc1343 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      1
-#define DO_TRACE_RELO        1
+#define DO_TRACE_LOOKUP      0
+#define DO_TRACE_RELO        0
 #define TIMING               0
 #define STATS                0
 #define COUNT_PAGES          0