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  *  Licensed under the Open Software License version 1.1
   8  *
   9  * Simple allocator for data that doesn't get partially free'd.
  10  * The tokenizer and parser allocate a _lot_ of small data structures
  11  * (often just two-three bytes for things like small integers),
  12  * and since they all depend on each other you can't free them
  13  * individually _anyway_. So do something that is very space-
  14  * efficient: allocate larger "blobs", and give out individual
  15  * small bits and pieces of it with no maintenance overhead.
  16  */
  17 #include <stdlib.h>
  18 #include <stddef.h>
  19 #include <stdio.h>
  20
  21 #include "lib.h"
  22 #include "allocate.h"
  23 #include "compat.h"
  24 #include "token.h"
  25 #include "symbol.h"
  26 #include "scope.h"
  27 #include "expression.h"
  28 #include "linearize.h"
  29
  30 void drop_all_allocations(struct allocator_struct *desc)
  31 {
  32         struct allocation_blob *blob = desc->blobs;
  33
  34         desc->blobs = NULL;
  35         desc->allocations = 0;
  36         desc->total_bytes = 0;
  37         desc->useful_bytes = 0;
  38         desc->freelist = NULL;
  39         while (blob) {
  40                 struct allocation_blob *next = blob->next;
  41                 blob_free(blob, desc->chunking);
  42                 blob = next;
  43         }
  44 }
  45
  46 void free_one_entry(struct allocator_struct *desc, void *entry)
  47 {
  48         void **p = entry;
  49         *p = desc->freelist;
  50         desc->freelist = p;
  51 }
  52
  53 void *allocate(struct allocator_struct *desc, unsigned int size)
  54 {
  55         unsigned long alignment = desc->alignment;
  56         struct allocation_blob *blob = desc->blobs;
  57         void *retval;
  58
  59         /*
  60          * NOTE! The freelist only works with things that are
  61          *  (a) sufficiently aligned
  62          *  (b) use a constant size
  63          * Don't try to free allocators that don't follow
  64          * these rules.
  65          */
  66         if (desc->freelist) {
  67                 void **p = desc->freelist;
  68                 retval = p;
  69                 desc->freelist = *p;
  70                 do {
  71                         *p = NULL;
  72                         p++;
  73                 } while ((size -= sizeof(void *)) > 0);
  74                 return retval;
  75         }
  76
  77         desc->allocations++;
  78         desc->useful_bytes += size;
  79         size = (size + alignment - 1) & ~(alignment-1);
  80         if (!blob || blob->left < size) {
  81                 unsigned int offset, chunking = desc->chunking;
  82                 struct allocation_blob *newblob = blob_alloc(chunking);
  83                 if (!newblob)
  84                         die("out of memory");
  85                 desc->total_bytes += chunking;
  86                 newblob->next = blob;
  87                 blob = newblob;
  88                 desc->blobs = newblob;
  89                 offset = offsetof(struct allocation_blob, data);
  90                 offset = (offset + alignment - 1) & ~(alignment-1);
  91                 blob->left = chunking - offset;
  92                 blob->offset = offset - offsetof(struct allocation_blob, data);
  93         }
  94         retval = blob->data + blob->offset;
  95         blob->offset += size;
  96         blob->left -= size;
  97         return retval;
  98 }
  99
 100 void show_allocations(struct allocator_struct *x)
 101 {
 102         fprintf(stderr, "%s: %d allocations, %d bytes (%d total bytes, "
 103                         "%6.2f%% usage, %6.2f average size)\n",
 104                 x->name, x->allocations, x->useful_bytes, x->total_bytes,
 105                 100 * (double) x->useful_bytes / x->total_bytes,
 106                 (double) x->useful_bytes / x->allocations);
 107 }
 108
 109 ALLOCATOR(ident, "identifiers");
 110 ALLOCATOR(token, "tokens");
 111 ALLOCATOR(symbol, "symbols");
 112 ALLOCATOR(expression, "expressions");
 113 ALLOCATOR(statement, "statements");
 114 ALLOCATOR(string, "strings");
 115 ALLOCATOR(scope, "scopes");
 116 __ALLOCATOR(void, 0, 1, "bytes", bytes);
 117 ALLOCATOR(basic_block, "basic_block");
 118 ALLOCATOR(entrypoint, "entrypoint");
 119 ALLOCATOR(instruction, "instruction");
 120 ALLOCATOR(multijmp, "multijmp");
 121 ALLOCATOR(pseudo, "pseudo");
 122
 123