From af7315acf6a3a5ac329b04cb543b5d8a95dc26f1 Mon Sep 17 00:00:00 2001 From: Iliyan Malchev Date: Fri, 16 Oct 2009 17:50:42 -0700 Subject: bionic/linker: change the buddy allocator to take a handle to the managed area -- rename struct ba_info to struct ba -- move the static ba descriptor from ba.c to linker.c and rename it ba_prelink -- ba_init, ba_allocate, ba_free, ba_start_addr, and ba_len all take a pointer to struct ba Signed-off-by: Iliyan Malchev --- linker/ba.c | 71 ++++++++++++++++----------------------------------------- linker/ba.h | 31 +++++++++++++++++++++---- linker/linker.c | 24 ++++++++++++++----- 3 files changed, 64 insertions(+), 62 deletions(-) diff --git a/linker/ba.c b/linker/ba.c index bea6f84..8534919 100644 --- a/linker/ba.c +++ b/linker/ba.c @@ -30,65 +30,34 @@ #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_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]), -}; +#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) -void ba_init(void) +void ba_init(struct ba *ba) { int i, index = 0; - for (i = sizeof(ba.num_entries) * 8 - 1; i >= 0; i--) { - if (ba.num_entries & 1<num_entries) * 8 - 1; i >= 0; i--) { + if (ba->num_entries & 1<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 @@ -103,16 +72,16 @@ int ba_free(int index) } else { break; } - } while (curr < ba.num_entries); + } while (curr < ba->num_entries); return 0; } -static unsigned long ba_order(unsigned long len) +static unsigned long ba_order(struct ba *ba, unsigned long len) { unsigned long i; - len = (len + BA_MIN_ALLOC - 1) / BA_MIN_ALLOC; + len = (len + ba->min_alloc - 1) / ba->min_alloc; len--; for (i = 0; i < sizeof(len)*8; i++) if (len >> i == 0) @@ -120,14 +89,14 @@ static unsigned long ba_order(unsigned long len) return i; } -int ba_allocate(unsigned long len) +int ba_allocate(struct ba *ba, unsigned long len) { int curr = 0; - int end = ba.num_entries; + int end = ba->num_entries; int best_fit = -1; - unsigned long order = ba_order(len); + unsigned long order = ba_order(ba, len); - if (order > BA_MAX_ORDER) + if (order > ba->max_order) return -1; /* look through the bitmap: @@ -165,16 +134,16 @@ int ba_allocate(unsigned long len) buddy = BA_BUDDY_INDEX(best_fit); BA_ORDER(buddy) = BA_ORDER(best_fit); } - ba.bitmap[best_fit].allocated = 1; + ba->bitmap[best_fit].allocated = 1; return best_fit; } -unsigned long ba_start_addr(int index) +unsigned long ba_start_addr(struct ba *ba, int index) { return BA_START_ADDR(index); } -unsigned long ba_len(int index) +unsigned long ba_len(struct ba *ba, int index) { return BA_LEN(index); } diff --git a/linker/ba.h b/linker/ba.h index 78f4626..c11017b 100644 --- a/linker/ba.h +++ b/linker/ba.h @@ -29,10 +29,31 @@ #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); +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 a6ecd1a..07c7d78 100644 --- a/linker/linker.c +++ b/linker/linker.c @@ -91,6 +91,18 @@ static soinfo *sonext = &libdl_info; static soinfo *somain; /* main process, always the one after libdl_info */ #endif + +/* Set up for the buddy allocator managing the prelinked libraries. */ +static struct ba_bits ba_prelink_bitmap[(LIBLAST - LIBBASE) / LIBINC]; +static struct ba ba_prelink = { + .base = LIBBASE, + .size = LIBLAST - LIBBASE, + .min_alloc = LIBINC, + .max_order = 128, + .bitmap = ba_prelink_bitmap, + .num_entries = sizeof(ba_prelink_bitmap)/sizeof(ba_prelink_bitmap[0]), +}; + static inline int validate_soinfo(soinfo *si) { return (si >= sopool && si < sopool + SO_MAX) || @@ -783,14 +795,14 @@ alloc_mem_region(soinfo *si) for it from the buddy allocator, which manages the area between LIBBASE and LIBLAST. */ - si->ba_index = ba_allocate(si->size); + si->ba_index = ba_allocate(&ba_prelink, si->size); if(si->ba_index >= 0) { - si->base = ba_start_addr(si->ba_index); + si->base = ba_start_addr(&ba_prelink, 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); + ba_free(&ba_prelink, si->ba_index); si->ba_index = -1; si->base = 0; goto err; @@ -1086,7 +1098,7 @@ 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(si->ba_index); + ba_free(&ba_prelink, si->ba_index); si->ba_index = -1; } goto fail; @@ -1189,7 +1201,7 @@ unsigned unload_library(soinfo *si) PRINT("%5d releasing library '%s' address space at %08x "\ "through buddy allocator.\n", pid, si->name, si->base); - ba_free(si->ba_index); + ba_free(&ba_prelink, si->ba_index); } notify_gdb_of_unload(si); free_info(si); @@ -1897,7 +1909,7 @@ unsigned __linker_init(unsigned **elfdata) vecs += 2; } - ba_init(); + ba_init(&ba_prelink); si->base = 0; si->dynamic = (unsigned *)-1; -- cgit v1.1 From bb9eedeff4ddc4550991eb4511003bda8672d6c4 Mon Sep 17 00:00:00 2001 From: Iliyan Malchev Date: Mon, 19 Oct 2009 14:25:17 -0700 Subject: bionic/linker: make the buddy allocator compute max_order on its own Signed-off-by: Iliyan Malchev --- linker/ba.c | 7 +++++++ linker/linker.c | 2 +- 2 files changed, 8 insertions(+), 1 deletion(-) diff --git a/linker/ba.c b/linker/ba.c index 8534919..db49c4b 100644 --- a/linker/ba.c +++ b/linker/ba.c @@ -41,9 +41,16 @@ #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<