allocate.c

   1 /*
   2  * allocate.c - simple space-efficient blob allocator.
   3  *
   4  * Copyright (C) 2003 Transmeta Corp.
   5  *               2003-2004 Linus Torvalds
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  *
  25  * Simple allocator for data that doesn't get partially free'd.
  26  * The tokenizer and parser allocate a _lot_ of small data structures
  27  * (often just two-three bytes for things like small integers),
  28  * and since they all depend on each other you can't free them
  29  * individually _anyway_. So do something that is very space-
  30  * efficient: allocate larger "blobs", and give out individual
  31  * small bits and pieces of it with no maintenance overhead.
  32  */
  33 #include <stdlib.h>
  34 #include <stddef.h>
  35 #include <stdio.h>
  36
  37 #include "lib.h"
  38 #include "allocate.h"
  39 #include "compat.h"
  40 #include "token.h"
  41 #include "symbol.h"
  42 #include "scope.h"
  43 #include "expression.h"
  44 #include "linearize.h"
  45
  46 void protect_allocations(struct allocator_struct *desc)
  47 {
  48         desc->blobs = NULL;
  49 }
  50
  51 void drop_all_allocations(struct allocator_struct *desc)
  52 {
  53         struct allocation_blob *blob = desc->blobs;
  54
  55         desc->blobs = NULL;
  56         desc->allocations = 0;
  57         desc->total_bytes = 0;
  58         desc->useful_bytes = 0;
  59         desc->freelist = NULL;
  60         while (blob) {
  61                 struct allocation_blob *next = blob->next;
  62                 blob_free(blob, desc->chunking);
  63                 blob = next;
  64         }
  65 }
  66
  67 void free_one_entry(struct allocator_struct *desc, void *entry)
  68 {
  69         void **p = entry;
  70         *p = desc->freelist;
  71         desc->freelist = p;
  72 }
  73
  74 void *allocate(struct allocator_struct *desc, unsigned int size)
  75 {
  76         unsigned long alignment = desc->alignment;
  77         struct allocation_blob *blob = desc->blobs;
  78         void *retval;
  79
  80         /*
  81          * NOTE! The freelist only works with things that are
  82          *  (a) sufficiently aligned
  83          *  (b) use a constant size
  84          * Don't try to free allocators that don't follow
  85          * these rules.
  86          */
  87         if (desc->freelist) {
  88                 void **p = desc->freelist;
  89                 retval = p;
  90                 desc->freelist = *p;
  91                 do {
  92                         *p = NULL;
  93                         p++;
  94                 } while ((size -= sizeof(void *)) > 0);
  95                 return retval;
  96         }
  97
  98         desc->allocations++;
  99         desc->useful_bytes += size;
 100         size = (size + alignment - 1) & ~(alignment-1);
 101         if (!blob || blob->left < size) {
 102                 unsigned int offset, chunking = desc->chunking;
 103                 struct allocation_blob *newblob = blob_alloc(chunking);
 104                 if (!newblob)
 105                         die("out of memory");
 106                 desc->total_bytes += chunking;
 107                 newblob->next = blob;
 108                 blob = newblob;
 109                 desc->blobs = newblob;
 110                 offset = offsetof(struct allocation_blob, data);
 111                 offset = (offset + alignment - 1) & ~(alignment-1);
 112                 blob->left = chunking - offset;
 113                 blob->offset = offset - offsetof(struct allocation_blob, data);
 114         }
 115         retval = blob->data + blob->offset;
 116         blob->offset += size;
 117         blob->left -= size;
 118         return retval;
 119 }
 120
 121 void show_allocations(struct allocator_struct *x)
 122 {
 123         fprintf(stderr, "%s: %lu allocations, %lu bytes (%lu total bytes, "
 124                         "%6.2f%% usage, %6.2f average size)\n",
 125                 x->name, x->allocations, x->useful_bytes, x->total_bytes,
 126                 100 * (double) x->useful_bytes / x->total_bytes,
 127                 (double) x->useful_bytes / x->allocations);
 128 }
 129
 130 void get_allocator_stats(struct allocator_struct *x, struct allocator_stats *s)
 131 {
 132         s->name = x->name;
 133         s->allocations = x->allocations;
 134         s->useful_bytes = x->useful_bytes;
 135         s->total_bytes = x->total_bytes;
 136 }
 137
 138 ALLOCATOR(ident, "identifiers");
 139 ALLOCATOR(token, "tokens");
 140 ALLOCATOR(context, "contexts");
 141 ALLOCATOR(symbol, "symbols");
 142 ALLOCATOR(expression, "expressions");
 143 ALLOCATOR(statement, "statements");
 144 ALLOCATOR(string, "strings");
 145 ALLOCATOR(scope, "scopes");
 146 __DO_ALLOCATOR(void, 0, 1, "bytes", bytes);
 147 ALLOCATOR(basic_block, "basic_block");
 148 ALLOCATOR(entrypoint, "entrypoint");
 149 ALLOCATOR(instruction, "instruction");
 150 ALLOCATOR(multijmp, "multijmp");
 151 ALLOCATOR(pseudo, "pseudo");
 152
 153