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 protect_allocations(struct allocator_struct *desc)
  31 {
  32         desc->blobs = NULL;
  33 }
  34
  35 void drop_all_allocations(struct allocator_struct *desc)
  36 {
  37         struct allocation_blob *blob = desc->blobs;
  38
  39         desc->blobs = NULL;
  40         desc->allocations = 0;
  41         desc->total_bytes = 0;
  42         desc->useful_bytes = 0;
  43         desc->freelist = NULL;
  44         while (blob) {
  45                 struct allocation_blob *next = blob->next;
  46                 blob_free(blob, desc->chunking);
  47                 blob = next;
  48         }
  49 }
  50
  51 void free_one_entry(struct allocator_struct *desc, void *entry)
  52 {
  53         void **p = entry;
  54         *p = desc->freelist;
  55         desc->freelist = p;
  56 }
  57
  58 void *allocate(struct allocator_struct *desc, unsigned int size)
  59 {
  60         unsigned long alignment = desc->alignment;
  61         struct allocation_blob *blob = desc->blobs;
  62         void *retval;
  63
  64         /*
  65          * NOTE! The freelist only works with things that are
  66          *  (a) sufficiently aligned
  67          *  (b) use a constant size
  68          * Don't try to free allocators that don't follow
  69          * these rules.
  70          */
  71         if (desc->freelist) {
  72                 void **p = desc->freelist;
  73                 retval = p;
  74                 desc->freelist = *p;
  75                 do {
  76                         *p = NULL;
  77                         p++;
  78                 } while ((size -= sizeof(void *)) > 0);
  79                 return retval;
  80         }
  81
  82         desc->allocations++;
  83         desc->useful_bytes += size;
  84         size = (size + alignment - 1) & ~(alignment-1);
  85         if (!blob || blob->left < size) {
  86                 unsigned int offset, chunking = desc->chunking;
  87                 struct allocation_blob *newblob = blob_alloc(chunking);
  88                 if (!newblob)
  89                         die("out of memory");
  90                 desc->total_bytes += chunking;
  91                 newblob->next = blob;
  92                 blob = newblob;
  93                 desc->blobs = newblob;
  94                 offset = offsetof(struct allocation_blob, data);
  95                 offset = (offset + alignment - 1) & ~(alignment-1);
  96                 blob->left = chunking - offset;
  97                 blob->offset = offset - offsetof(struct allocation_blob, data);
  98         }
  99         retval = blob->data + blob->offset;
 100         blob->offset += size;
 101         blob->left -= size;
 102         return retval;
 103 }
 104
 105 void show_allocations(struct allocator_struct *x)
 106 {
 107         fprintf(stderr, "%s: %d allocations, %d bytes (%d total bytes, "
 108                         "%6.2f%% usage, %6.2f average size)\n",
 109                 x->name, x->allocations, x->useful_bytes, x->total_bytes,
 110                 100 * (double) x->useful_bytes / x->total_bytes,
 111                 (double) x->useful_bytes / x->allocations);
 112 }
 113
 114 ALLOCATOR(ident, "identifiers");
 115 ALLOCATOR(token, "tokens");
 116 ALLOCATOR(symbol, "symbols");
 117 ALLOCATOR(expression, "expressions");
 118 ALLOCATOR(statement, "statements");
 119 ALLOCATOR(string, "strings");
 120 ALLOCATOR(scope, "scopes");
 121 __ALLOCATOR(void, 0, 1, "bytes", bytes);
 122 ALLOCATOR(basic_block, "basic_block");
 123 ALLOCATOR(entrypoint, "entrypoint");
 124 ALLOCATOR(instruction, "instruction");
 125 ALLOCATOR(multijmp, "multijmp");
 126 ALLOCATOR(pseudo, "pseudo");
 127
 128