diff options
| author | Linus Torvalds <torvalds@ppc970.osdl.org> | 2004-12-02 12:08:51 -0700 |
|---|---|---|
| committer | Linus Torvalds <torvalds@ppc970.osdl.org> | 2005-04-07 21:05:25 -0700 |
| commit | 2035e136c41f24b9b991917fd0ead512e4fd3fd8 (patch) | |
| tree | 9151d61dd60d8f1d8087e9d97b62b89e1484ccfe | |
| parent | 34c0cd11a43671d68d47c99a895fb68dd920f0a5 (diff) | |
| download | sparse-dev-2035e136c41f24b9b991917fd0ead512e4fd3fd8.tar.gz | |
Split out the blob allocator from lib.c into allocate.c.
It's disgusting how intimate lib.c is with all the types,
and this is slowly trying to split things up a bit. Now
the intimate part is in allocate.c, but maybe we can get
to the point where each allocation user just declares its
own allocation strategy, and just uses the generic routines
in allocate.c
| -rw-r--r-- | Makefile | 5 | ||||
| -rw-r--r-- | allocate.c | 149 | ||||
| -rw-r--r-- | allocate.h | 46 | ||||
| -rw-r--r-- | check.c | 1 | ||||
| -rw-r--r-- | compat-cygwin.c | 1 | ||||
| -rw-r--r-- | compat-linux.c | 1 | ||||
| -rw-r--r-- | compat-mingw.c | 1 | ||||
| -rw-r--r-- | compat-solaris.c | 1 | ||||
| -rw-r--r-- | compile-i386.c | 1 | ||||
| -rw-r--r-- | compile.c | 1 | ||||
| -rw-r--r-- | evaluate.c | 1 | ||||
| -rw-r--r-- | expand.c | 1 | ||||
| -rw-r--r-- | expression.c | 2 | ||||
| -rw-r--r-- | expression.h | 2 | ||||
| -rw-r--r-- | inline.c | 1 | ||||
| -rw-r--r-- | lib.c | 145 | ||||
| -rw-r--r-- | lib.h | 23 | ||||
| -rw-r--r-- | obfuscate.c | 1 | ||||
| -rw-r--r-- | parse.c | 1 | ||||
| -rw-r--r-- | pre-process.c | 1 | ||||
| -rw-r--r-- | scope.c | 1 | ||||
| -rw-r--r-- | show-parse.c | 1 | ||||
| -rw-r--r-- | sort.c | 4 | ||||
| -rw-r--r-- | symbol.c | 1 | ||||
| -rw-r--r-- | test-linearize.c | 1 | ||||
| -rw-r--r-- | test-parsing.c | 1 | ||||
| -rw-r--r-- | test-sort.c | 1 | ||||
| -rw-r--r-- | tokenize.c | 1 |
28 files changed, 226 insertions, 170 deletions
@@ -12,11 +12,12 @@ PREFIX=$(HOME) PROGRAMS=test-lexing test-parsing obfuscate check compile test-linearize LIB_H= token.h parse.h lib.h symbol.h scope.h expression.h target.h \ - linearize.h bitmap.h ident-list.h compat.h flow.h + linearize.h bitmap.h ident-list.h compat.h flow.h allocate.h LIB_OBJS= target.o parse.o tokenize.o pre-process.o symbol.o lib.o scope.o \ expression.o show-parse.o evaluate.o expand.o inline.o linearize.o \ - sort.o flow.o cse.o simplify.o memops.o liveness.o compat-$(OS).o + sort.o allocate.o compat-$(OS).o \ + flow.o cse.o simplify.o memops.o liveness.o LIB_FILE= sparse.a LIBS=$(LIB_FILE) diff --git a/allocate.c b/allocate.c new file mode 100644 index 00000000..c3b39572 --- /dev/null +++ b/allocate.c @@ -0,0 +1,149 @@ +/* + * allocate.c - simple space-efficient blob allocator. + * + * Copyright (C) 2003 Transmeta Corp. + * 2003-2004 Linus Torvalds + * + * Licensed under the Open Software License version 1.1 + * + * Simple allocator for data that doesn't get partially free'd. + * The tokenizer and parser allocate a _lot_ of small data structures + * (often just two-three bytes for things like small integers), + * and since they all depend on each other you can't free them + * individually _anyway_. So do something that is very space- + * efficient: allocate larger "blobs", and give out individual + * small bits and pieces of it with no maintenance overhead. + */ +#include <stdlib.h> +#include <stddef.h> +#include <stdio.h> + +#include "lib.h" +#include "allocate.h" +#include "compat.h" +#include "token.h" +#include "symbol.h" +#include "scope.h" +#include "expression.h" +#include "linearize.h" + +void drop_all_allocations(struct allocator_struct *desc) +{ + struct allocation_blob *blob = desc->blobs; + + desc->blobs = NULL; + desc->allocations = 0; + desc->total_bytes = 0; + desc->useful_bytes = 0; + while (blob) { + struct allocation_blob *next = blob->next; + blob_free(blob, desc->chunking); + blob = next; + } +} + +void free_one_entry(struct allocator_struct *desc, void *entry) +{ + void **p = entry; + *p = desc->freelist; + desc->freelist = p; +} + +void *allocate(struct allocator_struct *desc, unsigned int size) +{ + unsigned long alignment = desc->alignment; + struct allocation_blob *blob = desc->blobs; + void *retval; + + /* + * NOTE! The freelist only works with things that are + * (a) sufficiently aligned + * (b) use a constant size + * Don't try to free allocators that don't follow + * these rules. + */ + if (desc->freelist) { + void **p = desc->freelist; + retval = p; + desc->freelist = *p; + do { + *p = NULL; + p++; + } while ((size -= sizeof(void *)) > 0); + return retval; + } + + desc->allocations++; + desc->useful_bytes += size; + size = (size + alignment - 1) & ~(alignment-1); + if (!blob || blob->left < size) { + unsigned int offset, chunking = desc->chunking; + struct allocation_blob *newblob = blob_alloc(chunking); + if (!newblob) + die("out of memory"); + desc->total_bytes += chunking; + newblob->next = blob; + blob = newblob; + desc->blobs = newblob; + offset = offsetof(struct allocation_blob, data); + offset = (offset + alignment - 1) & ~(alignment-1); + blob->left = chunking - offset; + blob->offset = offset - offsetof(struct allocation_blob, data); + } + retval = blob->data + blob->offset; + blob->offset += size; + blob->left -= size; + return retval; +} + +static void show_allocations(struct allocator_struct *x) +{ + fprintf(stderr, "%s: %d allocations, %d bytes (%d total bytes, " + "%6.2f%% usage, %6.2f average size)\n", + x->name, x->allocations, x->useful_bytes, x->total_bytes, + 100 * (double) x->useful_bytes / x->total_bytes, + (double) x->useful_bytes / x->allocations); +} + +struct allocator_struct ident_allocator = { "identifiers", NULL, __alignof__(struct ident), CHUNK }; +struct allocator_struct token_allocator = { "tokens", NULL, __alignof__(struct token), CHUNK }; +struct allocator_struct symbol_allocator = { "symbols", NULL, __alignof__(struct symbol), CHUNK }; +struct allocator_struct expression_allocator = { "expressions", NULL, __alignof__(struct expression), CHUNK }; +struct allocator_struct statement_allocator = { "statements", NULL, __alignof__(struct statement), CHUNK }; +struct allocator_struct string_allocator = { "strings", NULL, __alignof__(struct statement), CHUNK }; +struct allocator_struct scope_allocator = { "scopes", NULL, __alignof__(struct scope), CHUNK }; +struct allocator_struct bytes_allocator = { "bytes", NULL, 1, CHUNK }; +struct allocator_struct basic_block_allocator = { "basic_block", NULL, __alignof__(struct basic_block), CHUNK }; +struct allocator_struct entrypoint_allocator = { "entrypoint", NULL, __alignof__(struct entrypoint), CHUNK }; +struct allocator_struct instruction_allocator = { "instruction", NULL, __alignof__(struct instruction), CHUNK }; +struct allocator_struct multijmp_allocator = { "multijmp", NULL, __alignof__(struct multijmp), CHUNK }; +struct allocator_struct pseudo_allocator = { "pseudo", NULL, __alignof__(struct pseudo), CHUNK }; + +#define __ALLOCATOR(type, size, x) \ + type *__alloc_##x(int extra) \ + { \ + return allocate(&x##_allocator, size+extra); \ + } \ + void __free_##x(type *entry) \ + { \ + return free_one_entry(&x##_allocator, entry); \ + } \ + void show_##x##_alloc(void) \ + { \ + show_allocations(&x##_allocator); \ + } \ + void clear_##x##_alloc(void) \ + { \ + drop_all_allocations(&x##_allocator); \ + } +#define ALLOCATOR(x) __ALLOCATOR(struct x, sizeof(struct x), x) + +ALLOCATOR(ident); ALLOCATOR(token); ALLOCATOR(symbol); +ALLOCATOR(expression); ALLOCATOR(statement); ALLOCATOR(string); +ALLOCATOR(scope); __ALLOCATOR(void, 0, bytes); +ALLOCATOR(basic_block); ALLOCATOR(entrypoint); +ALLOCATOR(instruction); +ALLOCATOR(multijmp); +ALLOCATOR(pseudo); + + diff --git a/allocate.h b/allocate.h new file mode 100644 index 00000000..56abb0c7 --- /dev/null +++ b/allocate.h @@ -0,0 +1,46 @@ +#ifndef ALLOCATE_H +#define ALLOCATE_H + +struct allocation_blob { + struct allocation_blob *next; + unsigned int left, offset; + unsigned char data[]; +}; + +struct allocator_struct { + const char *name; + struct allocation_blob *blobs; + unsigned int alignment; + unsigned int chunking; + void *freelist; + /* statistics */ + unsigned int allocations, total_bytes, useful_bytes; +}; + +extern void drop_all_allocations(struct allocator_struct *desc); +extern void *allocate(struct allocator_struct *desc, unsigned int size); +extern void free_one_entry(struct allocator_struct *desc, void *entry); + +#define __DECLARE_ALLOCATOR(type, x) \ + extern type *__alloc_##x(int); \ + extern void __free_##x(type *); \ + extern void show_##x##_alloc(void); \ + extern void clear_##x##_alloc(void); +#define DECLARE_ALLOCATOR(x) __DECLARE_ALLOCATOR(struct x, x) + +DECLARE_ALLOCATOR(ident); +DECLARE_ALLOCATOR(token); +DECLARE_ALLOCATOR(symbol); +DECLARE_ALLOCATOR(expression); +DECLARE_ALLOCATOR(statement); +DECLARE_ALLOCATOR(string); +DECLARE_ALLOCATOR(scope); +__DECLARE_ALLOCATOR(void, bytes); +DECLARE_ALLOCATOR(basic_block); +DECLARE_ALLOCATOR(entrypoint); +DECLARE_ALLOCATOR(instruction); +DECLARE_ALLOCATOR(multijmp); +DECLARE_ALLOCATOR(phi); +DECLARE_ALLOCATOR(pseudo); + +#endif @@ -17,6 +17,7 @@ #include <fcntl.h> #include "lib.h" +#include "allocate.h" #include "token.h" #include "parse.h" #include "symbol.h" diff --git a/compat-cygwin.c b/compat-cygwin.c index 972d7c96..7545703d 100644 --- a/compat-cygwin.c +++ b/compat-cygwin.c @@ -13,6 +13,7 @@ #include <sys/stat.h> #include "lib.h" +#include "allocate.h" #include "token.h" void *blob_alloc(unsigned long size) diff --git a/compat-linux.c b/compat-linux.c index 8f621ae6..da24ab83 100644 --- a/compat-linux.c +++ b/compat-linux.c @@ -1,6 +1,7 @@ #define _GNU_SOURCE #include "lib.h" +#include "allocate.h" #include "compat/id-files-stat.c" #include "compat/mmap-blob.c" diff --git a/compat-mingw.c b/compat-mingw.c index 1941c0b0..66456c72 100644 --- a/compat-mingw.c +++ b/compat-mingw.c @@ -14,6 +14,7 @@ #include <string.h> #include "lib.h" +#include "allocate.h" #include "token.h" void *blob_alloc(unsigned long size) diff --git a/compat-solaris.c b/compat-solaris.c index d8fa1d9e..62a7714b 100644 --- a/compat-solaris.c +++ b/compat-solaris.c @@ -1,4 +1,5 @@ #include "lib.h" +#include "allocate.h" #include "compat/id-files-stat.c" #include "compat/mmap-blob.c" diff --git a/compile-i386.c b/compile-i386.c index eedd65b5..9e72a548 100644 --- a/compile-i386.c +++ b/compile-i386.c @@ -32,6 +32,7 @@ #include <assert.h> #include "lib.h" +#include "allocate.h" #include "token.h" #include "parse.h" #include "symbol.h" @@ -18,6 +18,7 @@ #include <fcntl.h> #include "lib.h" +#include "allocate.h" #include "token.h" #include "parse.h" #include "symbol.h" @@ -19,6 +19,7 @@ #include <limits.h> #include "lib.h" +#include "allocate.h" #include "parse.h" #include "token.h" #include "symbol.h" @@ -19,6 +19,7 @@ #include <limits.h> #include "lib.h" +#include "allocate.h" #include "parse.h" #include "token.h" #include "symbol.h" diff --git a/expression.c b/expression.c index 66aa6dfd..8a1b40e6 100644 --- a/expression.c +++ b/expression.c @@ -19,6 +19,8 @@ #include <limits.h> #include "lib.h" +#include "allocate.h" +#include "allocate.h" #include "token.h" #include "parse.h" #include "symbol.h" diff --git a/expression.h b/expression.h index c0b1292d..6f244fc6 100644 --- a/expression.h +++ b/expression.h @@ -11,6 +11,8 @@ * Declarations and helper functions for expression parsing. */ +#include "allocate.h" + struct expression_list; enum expression_type { @@ -11,6 +11,7 @@ #include <stdio.h> #include "lib.h" +#include "allocate.h" #include "token.h" #include "parse.h" #include "symbol.h" @@ -20,6 +20,7 @@ #include <sys/stat.h> #include "lib.h" +#include "allocate.h" #include "token.h" #include "parse.h" #include "symbol.h" @@ -70,150 +71,6 @@ unsigned int hexval(unsigned int c) return retval; } -/* - * Simple allocator for data that doesn't get partially free'd. - * The tokenizer and parser allocate a _lot_ of small data structures - * (often just two-three bytes for things like small integers), - * and since they all depend on each other you can't free them - * individually _anyway_. So do something that is very space- - * efficient: allocate larger "blobs", and give out individual - * small bits and pieces of it with no maintenance overhead. - */ -struct allocation_blob { - struct allocation_blob *next; - unsigned int left, offset; - unsigned char data[]; -}; - -struct allocator_struct { - const char *name; - struct allocation_blob *blobs; - unsigned int alignment; - unsigned int chunking; - void *freelist; - /* statistics */ - unsigned int allocations, total_bytes, useful_bytes; -}; - -void drop_all_allocations(struct allocator_struct *desc) -{ - struct allocation_blob *blob = desc->blobs; - - desc->blobs = NULL; - desc->allocations = 0; - desc->total_bytes = 0; - desc->useful_bytes = 0; - while (blob) { - struct allocation_blob *next = blob->next; - blob_free(blob, desc->chunking); - blob = next; - } -} - -void free_one_entry(struct allocator_struct *desc, void *entry) -{ - void **p = entry; - *p = desc->freelist; - desc->freelist = p; -} - -void *allocate(struct allocator_struct *desc, unsigned int size) -{ - unsigned long alignment = desc->alignment; - struct allocation_blob *blob = desc->blobs; - void *retval; - - /* - * NOTE! The freelist only works with things that are - * (a) sufficiently aligned - * (b) use a constant size - * Don't try to free allocators that don't follow - * these rules. - */ - if (desc->freelist) { - void **p = desc->freelist; - retval = p; - desc->freelist = *p; - do { - *p = NULL; - p++; - } while ((size -= sizeof(void *)) > 0); - return retval; - } - - desc->allocations++; - desc->useful_bytes += size; - size = (size + alignment - 1) & ~(alignment-1); - if (!blob || blob->left < size) { - unsigned int offset, chunking = desc->chunking; - struct allocation_blob *newblob = blob_alloc(chunking); - if (!newblob) - die("out of memory"); - desc->total_bytes += chunking; - newblob->next = blob; - blob = newblob; - desc->blobs = newblob; - offset = offsetof(struct allocation_blob, data); - offset = (offset + alignment - 1) & ~(alignment-1); - blob->left = chunking - offset; - blob->offset = offset - offsetof(struct allocation_blob, data); - } - retval = blob->data + blob->offset; - blob->offset += size; - blob->left -= size; - return retval; -} - -static void show_allocations(struct allocator_struct *x) -{ - fprintf(stderr, "%s: %d allocations, %d bytes (%d total bytes, " - "%6.2f%% usage, %6.2f average size)\n", - x->name, x->allocations, x->useful_bytes, x->total_bytes, - 100 * (double) x->useful_bytes / x->total_bytes, - (double) x->useful_bytes / x->allocations); -} - -struct allocator_struct ident_allocator = { "identifiers", NULL, __alignof__(struct ident), CHUNK }; -struct allocator_struct token_allocator = { "tokens", NULL, __alignof__(struct token), CHUNK }; -struct allocator_struct symbol_allocator = { "symbols", NULL, __alignof__(struct symbol), CHUNK }; -struct allocator_struct expression_allocator = { "expressions", NULL, __alignof__(struct expression), CHUNK }; -struct allocator_struct statement_allocator = { "statements", NULL, __alignof__(struct statement), CHUNK }; -struct allocator_struct string_allocator = { "strings", NULL, __alignof__(struct statement), CHUNK }; -struct allocator_struct scope_allocator = { "scopes", NULL, __alignof__(struct scope), CHUNK }; -struct allocator_struct bytes_allocator = { "bytes", NULL, 1, CHUNK }; -struct allocator_struct basic_block_allocator = { "basic_block", NULL, __alignof__(struct basic_block), CHUNK }; -struct allocator_struct entrypoint_allocator = { "entrypoint", NULL, __alignof__(struct entrypoint), CHUNK }; -struct allocator_struct instruction_allocator = { "instruction", NULL, __alignof__(struct instruction), CHUNK }; -struct allocator_struct multijmp_allocator = { "multijmp", NULL, __alignof__(struct multijmp), CHUNK }; -struct allocator_struct pseudo_allocator = { "pseudo", NULL, __alignof__(struct pseudo), CHUNK }; - -#define __ALLOCATOR(type, size, x) \ - type *__alloc_##x(int extra) \ - { \ - return allocate(&x##_allocator, size+extra); \ - } \ - void __free_##x(type *entry) \ - { \ - return free_one_entry(&x##_allocator, entry); \ - } \ - void show_##x##_alloc(void) \ - { \ - show_allocations(&x##_allocator); \ - } \ - void clear_##x##_alloc(void) \ - { \ - drop_all_allocations(&x##_allocator); \ - } -#define ALLOCATOR(x) __ALLOCATOR(struct x, sizeof(struct x), x) - -ALLOCATOR(ident); ALLOCATOR(token); ALLOCATOR(symbol); -ALLOCATOR(expression); ALLOCATOR(statement); ALLOCATOR(string); -ALLOCATOR(scope); __ALLOCATOR(void, 0, bytes); -ALLOCATOR(basic_block); ALLOCATOR(entrypoint); -ALLOCATOR(instruction); -ALLOCATOR(multijmp); -ALLOCATOR(pseudo); - int ptr_list_size(struct ptr_list *head) { int nr = 0; @@ -75,29 +75,6 @@ extern void error(struct position, const char *, ...) FORMAT_ATTR(2); extern void error_die(struct position, const char *, ...) FORMAT_ATTR(2); #undef FORMAT_ATTR -#define __DECLARE_ALLOCATOR(type, x) \ - extern type *__alloc_##x(int); \ - extern void __free_##x(type *); \ - extern void show_##x##_alloc(void); \ - extern void clear_##x##_alloc(void); -#define DECLARE_ALLOCATOR(x) __DECLARE_ALLOCATOR(struct x, x) - -DECLARE_ALLOCATOR(ident); -DECLARE_ALLOCATOR(token); -DECLARE_ALLOCATOR(symbol); -DECLARE_ALLOCATOR(expression); -DECLARE_ALLOCATOR(statement); -DECLARE_ALLOCATOR(string); -DECLARE_ALLOCATOR(scope); -__DECLARE_ALLOCATOR(void, bytes); -DECLARE_ALLOCATOR(basic_block); -DECLARE_ALLOCATOR(entrypoint); -DECLARE_ALLOCATOR(instruction); -DECLARE_ALLOCATOR(multijmp); -DECLARE_ALLOCATOR(phi); -DECLARE_ALLOCATOR(pseudo); - - #define LIST_NODE_NR (29) struct ptr_list { diff --git a/obfuscate.c b/obfuscate.c index aa1a32fd..12fb9c39 100644 --- a/obfuscate.c +++ b/obfuscate.c @@ -17,6 +17,7 @@ #include <fcntl.h> #include "lib.h" +#include "allocate.h" #include "token.h" #include "parse.h" #include "symbol.h" @@ -19,6 +19,7 @@ #include <limits.h> #include "lib.h" +#include "allocate.h" #include "token.h" #include "parse.h" #include "symbol.h" diff --git a/pre-process.c b/pre-process.c index d243766a..950aea37 100644 --- a/pre-process.c +++ b/pre-process.c @@ -21,6 +21,7 @@ #include "pre-process.h" #include "lib.h" +#include "allocate.h" #include "parse.h" #include "token.h" #include "symbol.h" @@ -12,6 +12,7 @@ #include <string.h> #include "lib.h" +#include "allocate.h" #include "symbol.h" #include "scope.h" diff --git a/show-parse.c b/show-parse.c index 3516991d..2b8e4715 100644 --- a/show-parse.c +++ b/show-parse.c @@ -17,6 +17,7 @@ #include <fcntl.h> #include "lib.h" +#include "allocate.h" #include "token.h" #include "parse.h" #include "symbol.h" @@ -9,11 +9,13 @@ * Stable: yes. */ -#include "lib.h" #include <stdio.h> #include <stdlib.h> #include <string.h> +#include "lib.h" +#include "allocate.h" + #undef PARANOIA #undef COVERAGE @@ -12,6 +12,7 @@ #include <string.h> #include "lib.h" +#include "allocate.h" #include "token.h" #include "parse.h" #include "symbol.h" diff --git a/test-linearize.c b/test-linearize.c index 75826a0c..df233299 100644 --- a/test-linearize.c +++ b/test-linearize.c @@ -15,6 +15,7 @@ #include <fcntl.h> #include "lib.h" +#include "allocate.h" #include "token.h" #include "parse.h" #include "symbol.h" diff --git a/test-parsing.c b/test-parsing.c index 59ae4be6..7f6f4bf4 100644 --- a/test-parsing.c +++ b/test-parsing.c @@ -17,6 +17,7 @@ #include <fcntl.h> #include "lib.h" +#include "allocate.h" #include "token.h" #include "parse.h" #include "symbol.h" diff --git a/test-sort.c b/test-sort.c index c259e2b6..d0ffb670 100644 --- a/test-sort.c +++ b/test-sort.c @@ -1,4 +1,5 @@ #include "lib.h" +#include "allocate.h" #include <stdio.h> #include <stdlib.h> @@ -17,6 +17,7 @@ #include <sys/stat.h> #include "lib.h" +#include "allocate.h" #include "token.h" #include "symbol.h" |