linker: get rid of the buddy allocator

Currently, the Android linker is placing shared libraries into
a well-known spot in memory.  This is interfering with the kernel's
ASLR support.

This change stops forcing non-prelinked libraries into a particular
address space.

Also, get rid of FLAG_PRELINKED.  As best I can tell, this flag
is never used.

Change-Id: I527af12fb54f821c2b5ca7693dbf63d022f8f4ae

5 files changed, 15 insertions, 277 deletions

diff --git a/linker/Android.mk b/linker/Android.mk
index abe59951b..60f291ce0 100644
--- a/linker/Android.mk
+++ b/linker/Android.mk
@@ -8,8 +8,7 @@ LOCAL_SRC_FILES:= \
 	linker_format.c \
 	rt.c \
 	dlfcn.c \
-	debugger.c \
-	ba.c
+	debugger.c
 
 ifeq ($(TARGET_ARCH),sh)
 # SH-4A series virtual address range from 0x00000000 to 0x7FFFFFFF.
diff --git a/linker/ba.c b/linker/ba.c
deleted file mode 100644
index db49c4b42..000000000
--- a/linker/ba.c
+++ /dev/null
@@ -1,156 +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"
-
-#undef min
-#define min(a,b) ((a)<(b)?(a):(b))
-
-#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 unsigned long ba_order(struct ba *ba, unsigned long len);
-
-void ba_init(struct ba *ba)
-{
-    int i, index = 0;
-
-    unsigned long max_order = ba_order(ba, ba->size);
-    if (ba->max_order == 0 || ba->max_order > max_order)
-        ba->max_order = max_order;
-
-    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(struct ba *ba, 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(struct ba *ba, 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(struct ba *ba, unsigned long len)
-{
-    int curr = 0;
-    int end = ba->num_entries;
-    int best_fit = -1;
-    unsigned long order = ba_order(ba, 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(struct ba *ba, int index)
-{
-    return BA_START_ADDR(index);
-}
-
-unsigned long ba_len(struct ba *ba, int index)
-{
-    return BA_LEN(index);
-}
diff --git a/linker/ba.h b/linker/ba.h
deleted file mode 100644
index c11017bcd..000000000
--- a/linker/ba.h
+++ /dev/null
@@ -1,59 +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
-
-struct ba_bits {
-    unsigned allocated:1;           /* 1 if allocated, 0 if free */
-    unsigned order:7;               /* size of the region in ba space */
-};
-
-struct ba {
-    /* start address of the ba space */
-    unsigned long base;
-    /* total size of the ba space */
-    unsigned long size;
-    /* the smaller allocation that can be made */
-    unsigned long min_alloc;
-    /* the order of the largest allocation that can be made */
-    unsigned long max_order;
-    /* 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;
-};
-
-extern void ba_init(struct ba *ba);
-extern int ba_allocate(struct ba *ba, unsigned long len);
-extern int ba_free(struct ba *ba, int index);
-extern unsigned long ba_start_addr(struct ba *ba, int index);
-extern unsigned long ba_len(struct ba *ba, int index);
-
-#endif
diff --git a/linker/linker.c b/linker/linker.c
index e350d8978..4d850641d 100644
--- a/linker/linker.c
+++ b/linker/linker.c
@@ -51,8 +51,6 @@
 #include "linker_environ.h"
 #include "linker_format.h"
 
-#include "ba.h"
-
 #define ALLOW_SYMBOLS_FROM_MAIN 1
 #define SO_MAX 128
 
@@ -96,17 +94,6 @@ static soinfo *somain; /* main process, always the one after libdl_info */
 #endif
 
 
-/* Set up for the buddy allocator managing the non-prelinked libraries. */
-static struct ba_bits ba_nonprelink_bitmap[(LIBLAST - LIBBASE) / LIBINC];
-static struct ba ba_nonprelink = {
-    .base = LIBBASE,
-    .size = LIBLAST - LIBBASE,
-    .min_alloc = LIBINC,
-    /* max_order will be determined automatically */
-    .bitmap = ba_nonprelink_bitmap,
-    .num_entries = sizeof(ba_nonprelink_bitmap)/sizeof(ba_nonprelink_bitmap[0]),
-};
-
 static inline int validate_soinfo(soinfo *si)
 {
     return (si >= sopool && si < sopool + SO_MAX) ||
@@ -292,7 +279,6 @@ static soinfo *alloc_info(const char *name)
     memset(si, 0, sizeof(soinfo));
     strlcpy((char*) si->name, name, sizeof(si->name));
     sonext->next = si;
-    si->ba_index = -1; /* by default, prelinked */
     si->next = NULL;
     si->refcount = 0;
     sonext = si;
@@ -844,28 +830,25 @@ alloc_mem_region(soinfo *si)
 {
     if (si->base) {
         /* Attempt to mmap a prelinked library. */
-        si->ba_index = -1;
         return reserve_mem_region(si);
     }
 
-    /* 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.
+    /* This is not a prelinked library, so we use the kernel's default
+       allocator.
     */
-    si->ba_index = ba_allocate(&ba_nonprelink, si->size);
-    if(si->ba_index >= 0) {
-        si->base = ba_start_addr(&ba_nonprelink, 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(&ba_nonprelink, si->ba_index);
-            si->ba_index = -1;
-            si->base = 0;
-            goto err;
-        }
-        return 0;
+
+    void *base = mmap(NULL, si->size, PROT_READ | PROT_EXEC,
+                      MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+    if (base == MAP_FAILED) {
+        DL_ERR("%5d mmap of library '%s' failed: %d (%s)\n",
+              pid, si->name,
+              errno, strerror(errno));
+        goto err;
     }
+    si->base = (unsigned) base;
+    PRINT("%5d mapped library '%s' to %08x via kernel allocator.\n",
+          pid, si->name, si->base);
+    return 0;
 
 err:
     DL_ERR("OOPS: %5d cannot map library '%s'. no vspace available.",
@@ -1154,10 +1137,6 @@ load_library(const char *name)
 
     /* 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(&ba_nonprelink, si->ba_index);
-            si->ba_index = -1;
-        }
         goto fail;
     }
 
@@ -1187,9 +1166,6 @@ init_library(soinfo *si)
     TRACE("[ %5d init_library base=0x%08x sz=0x%08x name='%s') ]\n",
           pid, si->base, si->size, si->name);
 
-    if (si->base < LIBBASE || si->base >= LIBLAST)
-        si->flags |= FLAG_PRELINKED;
-
     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.
@@ -1264,12 +1240,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(&ba_nonprelink, si->ba_index);
-        }
         notify_gdb_of_unload(si);
         free_info(si);
         si->refcount = 0;
@@ -2213,8 +2183,6 @@ unsigned __linker_init(unsigned **elfdata)
         vecs += 2;
     }
 
-    ba_init(&ba_nonprelink);
-
     si->base = 0;
     si->dynamic = (unsigned *)-1;
     si->wrprotect_start = 0xffffffff;
diff --git a/linker/linker.h b/linker/linker.h
index 68ac275c4..301d26805 100644
--- a/linker/linker.h
+++ b/linker/linker.h
@@ -83,7 +83,6 @@ typedef struct soinfo soinfo;
 #define FLAG_LINKED     0x00000001
 #define FLAG_ERROR      0x00000002
 #define FLAG_EXE        0x00000004 // The main executable
-#define FLAG_PRELINKED  0x00000008 // This is a pre-linked lib
 
 #define SOINFO_NAME_LEN 128
 
@@ -95,8 +94,6 @@ struct soinfo
     unsigned entry;
     unsigned base;
     unsigned size;
-    // buddy-allocator index, negative for prelinked libraries
-    int ba_index;
 
     unsigned *dynamic;
 
@@ -154,17 +151,6 @@ struct soinfo
 
 extern soinfo libdl_info;
 
-/* these must all be powers of two */
-#ifdef ARCH_SH
-#define LIBBASE 0x60000000
-#define LIBLAST 0x70000000
-#define LIBINC  0x00100000
-#else
-#define LIBBASE 0x80000000
-#define LIBLAST 0x90000000
-#define LIBINC  0x00100000
-#endif
-
 #ifdef ANDROID_ARM_LINKER
 
 #define R_ARM_COPY       20