Revert "linker: get rid of the buddy allocator"
This reverts commit 7059b1f02ea9197728c851edd9ae0dd7688fa700.
Bug: 5036610
diff --git a/linker/Android.mk b/linker/Android.mk
index 60f291c..abe5995 100644
--- a/linker/Android.mk
+++ b/linker/Android.mk
@@ -8,7 +8,8 @@
linker_format.c \
rt.c \
dlfcn.c \
- debugger.c
+ debugger.c \
+ ba.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
new file mode 100644
index 0000000..db49c4b
--- /dev/null
+++ b/linker/ba.c
@@ -0,0 +1,156 @@
+/*
+ * 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
new file mode 100644
index 0000000..c11017b
--- /dev/null
+++ b/linker/ba.h
@@ -0,0 +1,59 @@
+/*
+ * 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 4d85064..e350d89 100644
--- a/linker/linker.c
+++ b/linker/linker.c
@@ -51,6 +51,8 @@
#include "linker_environ.h"
#include "linker_format.h"
+#include "ba.h"
+
#define ALLOW_SYMBOLS_FROM_MAIN 1
#define SO_MAX 128
@@ -94,6 +96,17 @@
#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) ||
@@ -279,6 +292,7 @@
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;
@@ -830,25 +844,28 @@
{
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 use the kernel's default
- allocator.
+ /* 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.
*/
-
- 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->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;
}
- 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.",
@@ -1137,6 +1154,10 @@
/* 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;
}
@@ -1166,6 +1187,9 @@
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.
@@ -1240,6 +1264,12 @@
}
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;
@@ -2183,6 +2213,8 @@
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 301d268..68ac275 100644
--- a/linker/linker.h
+++ b/linker/linker.h
@@ -83,6 +83,7 @@
#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
@@ -94,6 +95,8 @@
unsigned entry;
unsigned base;
unsigned size;
+ // buddy-allocator index, negative for prelinked libraries
+ int ba_index;
unsigned *dynamic;
@@ -151,6 +154,17 @@
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