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