lib.c

   1 /*
   2  * 'sparse' library helper routines.
   3  *
   4  * Copyright (C) 2003 Transmeta Corp.
   5  *               2003 Linus Torvalds
   6  *
   7  *  Licensed under the Open Software License version 1.1
   8  */
   9 #include <ctype.h>
  10 #include <fcntl.h>
  11 #include <stdarg.h>
  12 #include <stddef.h>
  13 #include <stdio.h>
  14 #include <stdlib.h>
  15 #include <string.h>
  16
  17 #include <sys/mman.h>
  18 #include <sys/types.h>
  19 #include <sys/stat.h>
  20
  21 #include "lib.h"
  22 #include "token.h"
  23 #include "parse.h"
  24 #include "symbol.h"
  25 #include "expression.h"
  26 #include "scope.h"
  27
  28 struct token *skip_to(struct token *token, int op)
  29 {
  30         while (!match_op(token, op) && !eof_token(token))
  31                 token = token->next;
  32         return token;
  33 }
  34
  35 struct token *expect(struct token *token, int op, const char *where)
  36 {
  37         if (!match_op(token, op)) {
  38                 static struct token bad_token;
  39                 if (token != &bad_token) {
  40                         bad_token.next = token;
  41                         warn(token->pos, "Expected %s %s", show_special(op), where);
  42                         warn(token->pos, "got %s", show_token(token));
  43                 }
  44                 if (op == ';')
  45                         return skip_to(token, op);
  46                 return &bad_token;
  47         }
  48         return token->next;
  49 }
  50
  51 unsigned int hexval(unsigned int c)
  52 {
  53         int retval = 256;
  54         switch (c) {
  55         case '0'...'9':
  56                 retval = c - '0';
  57                 break;
  58         case 'a'...'f':
  59                 retval = c - 'a' + 10;
  60                 break;
  61         case 'A'...'F':
  62                 retval = c - 'A' + 10;
  63                 break;
  64         }
  65         return retval;
  66 }
  67
  68 /*
  69  * Simple allocator for data that doesn't get partially free'd.
  70  * The tokenizer and parser allocate a _lot_ of small data structures
  71  * (often just two-three bytes for things like small integers),
  72  * and since they all depend on each other you can't free them
  73  * individually _anyway_. So do something that is very space-
  74  * efficient: allocate larger "blobs", and give out individual
  75  * small bits and pieces of it with no maintenance overhead.
  76  */
  77 struct allocation_blob {
  78         struct allocation_blob *next;
  79         unsigned int left, offset;
  80         unsigned char data[];
  81 };
  82
  83 #define CHUNK 32768
  84 #define blob_alloc(size) mmap(NULL, ((size)+4095) & ~4095, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0)
  85 #define blob_free(addr,size) munmap((addr), ((size)+4095) & ~4095)
  86
  87 struct allocator_struct {
  88         const char *name;
  89         struct allocation_blob *blobs;
  90         unsigned int alignment;
  91         unsigned int chunking;
  92         /* statistics */
  93         unsigned int allocations, total_bytes, useful_bytes;
  94 };
  95
  96 void drop_all_allocations(struct allocator_struct *desc)
  97 {
  98         struct allocation_blob *blob = desc->blobs;
  99
 100         desc->blobs = NULL;
 101         desc->allocations = 0;
 102         desc->total_bytes = 0;
 103         desc->useful_bytes = 0;
 104         while (blob) {
 105                 struct allocation_blob *next = blob->next;
 106                 blob_free(blob, desc->chunking);
 107                 blob = next;
 108         }
 109 }
 110
 111 void *allocate(struct allocator_struct *desc, unsigned int size)
 112 {
 113         unsigned long alignment = desc->alignment;
 114         struct allocation_blob *blob = desc->blobs;
 115         void *retval;
 116
 117         desc->allocations++;
 118         desc->useful_bytes += size;
 119         size = (size + alignment - 1) & ~(alignment-1);
 120         if (!blob || blob->left < size) {
 121                 unsigned int offset, chunking = desc->chunking;
 122                 struct allocation_blob *newblob = blob_alloc(chunking);
 123                 if (!newblob)
 124                         die("out of memory");
 125                 desc->total_bytes += chunking;
 126                 newblob->next = blob;
 127                 blob = newblob;
 128                 desc->blobs = newblob;
 129                 offset = offsetof(struct allocation_blob, data);
 130                 if (alignment > offset)
 131                         offset = alignment;
 132                 blob->left = chunking - offset;
 133                 blob->offset = offset - offsetof(struct allocation_blob, data);
 134         }
 135         retval = blob->data + blob->offset;
 136         blob->offset += size;
 137         blob->left -= size;
 138         return retval;
 139 }
 140
 141 static void show_allocations(struct allocator_struct *x)
 142 {
 143         fprintf(stderr, "%s: %d allocations, %d bytes (%d total bytes, "
 144                         "%6.2f%% usage, %6.2f average size)\n",
 145                 x->name, x->allocations, x->useful_bytes, x->total_bytes,
 146                 100 * (double) x->useful_bytes / x->total_bytes,
 147                 (double) x->useful_bytes / x->allocations);
 148 }
 149
 150 struct allocator_struct ident_allocator = { "identifiers", NULL, __alignof__(struct ident), CHUNK };
 151 struct allocator_struct token_allocator = { "tokens", NULL, __alignof__(struct token), CHUNK };
 152 struct allocator_struct symbol_allocator = { "symbols", NULL, __alignof__(struct symbol), CHUNK };
 153 struct allocator_struct expression_allocator = { "expressions", NULL, __alignof__(struct expression), CHUNK };
 154 struct allocator_struct statement_allocator = { "statements", NULL, __alignof__(struct statement), CHUNK };
 155 struct allocator_struct string_allocator = { "strings", NULL, __alignof__(struct statement), CHUNK };
 156 struct allocator_struct scope_allocator = { "scopes", NULL, __alignof__(struct scope), CHUNK };
 157 struct allocator_struct bytes_allocator = { "bytes", NULL, 1, CHUNK };
 158
 159 #define __ALLOCATOR(type, size, x)                              \
 160         type *__alloc_##x(int extra)                            \
 161         {                                                       \
 162                 return allocate(&x##_allocator, size+extra);    \
 163         }                                                       \
 164         void show_##x##_alloc(void)                             \
 165         {                                                       \
 166                 show_allocations(&x##_allocator);               \
 167         }                                                       \
 168         void clear_##x##_alloc(void)                            \
 169         {                                                       \
 170                 drop_all_allocations(&x##_allocator);           \
 171         }
 172 #define ALLOCATOR(x) __ALLOCATOR(struct x, sizeof(struct x), x)
 173
 174 ALLOCATOR(ident); ALLOCATOR(token); ALLOCATOR(symbol);
 175 ALLOCATOR(expression); ALLOCATOR(statement); ALLOCATOR(string);
 176 ALLOCATOR(scope); __ALLOCATOR(void, 0, bytes);
 177
 178 int ptr_list_size(struct ptr_list *head)
 179 {
 180         int nr = 0;
 181
 182         if (head) {
 183                 struct ptr_list *list = head;
 184                 do {
 185                         nr += list->nr;
 186                 } while ((list = list->next) != head);
 187         }
 188         return nr;
 189 }
 190
 191 void iterate(struct ptr_list *head, void (*callback)(void *, void *, int), void *data)
 192 {
 193         struct ptr_list *list = head;
 194         int flag = ITERATE_FIRST;
 195
 196         if (!head)
 197                 return;
 198         do {
 199                 int i;
 200                 for (i = 0; i < list->nr; i++) {
 201                         if (i == list->nr-1 && list->next == head)
 202                                 flag |= ITERATE_LAST;
 203                         callback(list->list[i], data, flag);
 204                         flag = 0;
 205                 }
 206                 list = list->next;
 207         } while (list != head);
 208 }
 209
 210 void add_ptr_list(struct ptr_list **listp, void *ptr)
 211 {
 212         struct ptr_list *list = *listp;
 213         int nr;
 214
 215         if (!list || (nr = list->nr) >= LIST_NODE_NR) {
 216                 struct ptr_list *newlist = malloc(sizeof(*newlist));
 217                 if (!newlist)
 218                         die("out of memory for symbol/statement lists");
 219                 memset(newlist, 0, sizeof(*newlist));
 220                 if (!list) {
 221                         newlist->next = newlist;
 222                         newlist->prev = newlist;
 223                         *listp = newlist;
 224                 } else {
 225                         newlist->next = list;
 226                         newlist->prev = list->prev;
 227                         list->prev->next = newlist;
 228                         list->prev = newlist;
 229                 }
 230                 list = newlist;
 231                 nr = 0;
 232         }
 233         list->list[nr] = ptr;
 234         nr++;
 235         list->nr = nr;
 236 }
 237
 238 void free_ptr_list(struct ptr_list **listp)
 239 {
 240         struct ptr_list *tmp, *list = *listp;
 241
 242         if (!list)
 243                 return;
 244
 245         list->prev->next = NULL;
 246         while (list) {
 247                 tmp = list;
 248                 list = list->next;
 249                 free(tmp);
 250         }
 251
 252         *listp = NULL;
 253 }
 254
 255 static void do_warn(const char *type, struct position pos, const char * fmt, va_list args)
 256 {
 257         static char buffer[512];
 258         const char *name;
 259
 260         vsprintf(buffer, fmt, args);
 261         name = input_streams[pos.stream].name;
 262
 263         fprintf(stderr, "%s: %s:%d:%d: %s\n",
 264                 type, name, pos.line, pos.pos, buffer);
 265 }
 266
 267 void warn(struct position pos, const char * fmt, ...)
 268 {
 269         static int warnings = 0;
 270         va_list args;
 271
 272         if (warnings > 100) {
 273                 static int once = 0;
 274                 if (once)
 275                         return;
 276                 fmt = "too many warnings";
 277                 once = 1;
 278         }
 279
 280         va_start(args, fmt);
 281         do_warn("warning", pos, fmt, args);
 282         va_end(args);
 283         warnings++;
 284 }
 285
 286 void error(struct position pos, const char * fmt, ...)
 287 {
 288         va_list args;
 289         va_start(args, fmt);
 290         do_warn("error", pos, fmt, args);
 291         va_end(args);
 292         exit(1);
 293 }
 294
 295 void die(const char *fmt, ...)
 296 {
 297         va_list args;
 298         static char buffer[512];
 299
 300         va_start(args, fmt);
 301         vsnprintf(buffer, sizeof(buffer), fmt, args);
 302         va_end(args);
 303
 304         fprintf(stderr, "%s\n", buffer);
 305         exit(1);
 306 }
 307
 308 unsigned int pre_buffer_size;
 309 unsigned char pre_buffer[8192];
 310
 311 int preprocess_only;
 312 char *include;
 313 int include_fd = -1;
 314
 315 void add_pre_buffer(const char *fmt, ...)
 316 {
 317         va_list args;
 318         unsigned int size;
 319
 320         va_start(args, fmt);
 321         size = pre_buffer_size;
 322         size += vsnprintf(pre_buffer + size,
 323                 sizeof(pre_buffer) - size,
 324                 fmt, args);
 325         pre_buffer_size = size;
 326         va_end(args);
 327 }
 328
 329 char **handle_switch_D(char *arg, char **next)
 330 {
 331         const char *name = arg + 1;
 332         const char *value = "";
 333         for (;;) {
 334                 char c;
 335                 c = *++arg;
 336                 if (!c)
 337                         break;
 338                 if (isspace(c) || c == '=') {
 339                         *arg = '\0';
 340                         value = arg + 1;
 341                         break;
 342                 }
 343         }
 344         add_pre_buffer("#define %s %s\n", name, value);
 345         return next;
 346 }
 347
 348 char **handle_switch_E(char *arg, char **next)
 349 {
 350         preprocess_only = 1;
 351         return next;
 352 }
 353
 354 char **handle_switch_v(char *arg, char **next)
 355 {
 356         verbose = 1;
 357         return next;
 358 }
 359 char **handle_switch_I(char *arg, char **next)
 360 {
 361         add_pre_buffer("#add_include \"%s/\"\n", arg + 1);
 362         return next;
 363 }
 364
 365 char **handle_switch_i(char *arg, char **next)
 366 {
 367         if (*next && !strcmp(arg, "include")) {
 368                 char *name = *++next;
 369                 int fd = open(name, O_RDONLY);
 370
 371                 include_fd = fd;
 372                 include = name;
 373                 if (fd < 0)
 374                         perror(name);
 375         }
 376         return next;
 377 }
 378
 379 char **handle_switch(char *arg, char **next)
 380 {
 381         char **rc = next;
 382
 383         switch (*arg) {
 384         case 'D': rc = handle_switch_D(arg, next); break;
 385         case 'E': rc = handle_switch_E(arg, next); break;
 386         case 'v': rc = handle_switch_v(arg, next); break;
 387         case 'I': rc = handle_switch_I(arg, next); break;
 388         case 'i': rc = handle_switch_i(arg, next); break;
 389         default:
 390                 /*
 391                  * Ignore unknown command line options:
 392                  * they're probably gcc switches
 393                  */
 394                 break;
 395         }
 396         return rc;
 397 }
 398
 399 void create_builtin_stream(void)
 400 {
 401         add_pre_buffer("#define __i386__ 1\n");
 402         add_pre_buffer("#define __linux__ 1\n");
 403         add_pre_buffer("#define __STDC__ 1\n");
 404         add_pre_buffer("#define linux linux\n");
 405         add_pre_buffer("#define cond_syscall(x)\n");
 406         add_pre_buffer("#define __GNUC__ 2\n");
 407         add_pre_buffer("#define __GNUC_MINOR__ 95\n");
 408         add_pre_buffer("#define __func__ \"function\"\n");
 409         add_pre_buffer("#define __extension__\n");
 410         add_pre_buffer("#define __pragma__\n");
 411         add_pre_buffer("#define __builtin_stdarg_start(a,b) ((a) = (__builtin_va_list)(&(b)))\n");
 412         add_pre_buffer("#define __builtin_va_arg(arg,type)  ((type)0)\n");
 413         add_pre_buffer("#define __builtin_va_end(arg)\n");
 414 }