git.gag.com Git - fw/altos/blob - src/lisp/ao_lisp_mem.c

   1 /*
   2  * Copyright © 2016 Keith Packard <keithp@keithp.com>
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation, either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  */
  14
  15 #define AO_LISP_CONST_BITS
  16
  17 #include "ao_lisp.h"
  18 #include <stdio.h>
  19
  20 #ifdef AO_LISP_MAKE_CONST
  21 #include <stdlib.h>
  22 uint8_t ao_lisp_const[AO_LISP_POOL_CONST] __attribute__((aligned(4)));
  23 #define ao_lisp_pool ao_lisp_const
  24 #undef AO_LISP_POOL
  25 #define AO_LISP_POOL AO_LISP_POOL_CONST
  26 #else
  27 uint8_t ao_lisp_pool[AO_LISP_POOL] __attribute__((aligned(4)));
  28 #endif
  29
  30 #if 0
  31 #define DBG_COLLECT_ALWAYS
  32 #endif
  33
  34 #if 0
  35 #define DBG_POOL
  36 #endif
  37
  38 #if 0
  39 #define DBG_INCLUDE
  40 #define DBG_DUMP        0
  41 #define DBG_OFFSET(a)   ((int) ((uint8_t *) (a) - ao_lisp_pool))
  42 #define DBG(...) printf(__VA_ARGS__)
  43 #define DBG_DO(a)       a
  44 static int move_dump;
  45 static int move_depth;
  46 #define DBG_RESET() (move_depth = 0)
  47 #define DBG_MOVE(...) do { if(move_dump) { int d; for (d = 0; d < move_depth; d++) printf ("  "); printf(__VA_ARGS__); } } while (0)
  48 #define DBG_MOVE_IN()   (move_depth++)
  49 #define DBG_MOVE_OUT()  (move_depth--)
  50 #else
  51 #define DBG(...)
  52 #define DBG_DO(a)
  53 #define DBG_RESET()
  54 #define DBG_MOVE(...)
  55 #define DBG_MOVE_IN()
  56 #define DBG_MOVE_OUT()
  57 #endif
  58
  59 uint8_t ao_lisp_exception;
  60
  61 struct ao_lisp_root {
  62         void                            **addr;
  63         const struct ao_lisp_type       *type;
  64 };
  65
  66 #define AO_LISP_ROOT    16
  67
  68 static struct ao_lisp_root      ao_lisp_root[AO_LISP_ROOT];
  69
  70 static uint8_t  ao_lisp_busy[AO_LISP_POOL / 32];
  71
  72 static uint8_t  ao_lisp_moving[AO_LISP_POOL / 32];
  73
  74 uint16_t        ao_lisp_top;
  75
  76 static inline void mark(uint8_t *tag, int offset) {
  77         int     byte = offset >> 5;
  78         int     bit = (offset >> 2) & 7;
  79         tag[byte] |= (1 << bit);
  80 }
  81
  82 static inline void clear(uint8_t *tag, int offset) {
  83         int     byte = offset >> 5;
  84         int     bit = (offset >> 2) & 7;
  85         tag[byte] &= ~(1 << bit);
  86 }
  87
  88 static inline int busy(uint8_t *tag, int offset) {
  89         int     byte = offset >> 5;
  90         int     bit = (offset >> 2) & 7;
  91         return (tag[byte] >> bit) & 1;
  92 }
  93
  94 static inline int min(int a, int b) { return a < b ? a : b; }
  95 static inline int max(int a, int b) { return a > b ? a : b; }
  96
  97 static inline int limit(int offset) {
  98         return min(AO_LISP_POOL, max(offset, 0));
  99 }
 100
 101 static int
 102 mark_object(uint8_t *tag, void *addr, int size) {
 103         int     base;
 104         int     bound;
 105
 106         if (!addr)
 107                 return 1;
 108
 109         if ((uint8_t *) addr < ao_lisp_pool || ao_lisp_pool + AO_LISP_POOL <= (uint8_t*) addr)
 110                 return 1;
 111
 112         base = (uint8_t *) addr - ao_lisp_pool;
 113         bound = base + size;
 114
 115         base = limit(base);
 116         bound = limit(bound);
 117         if (busy(tag, base))
 118                 return 1;
 119         while (base < bound) {
 120                 mark(tag, base);
 121                 base += 4;
 122         }
 123         return 0;
 124 }
 125
 126 static int
 127 clear_object(uint8_t *tag, void *addr, int size) {
 128         int     base;
 129         int     bound;
 130         if (!addr)
 131                 return 1;
 132
 133         base = (uint8_t *) addr - ao_lisp_pool;
 134         bound = base + size;
 135
 136         base = limit(base);
 137         bound = limit(bound);
 138         if (!busy(tag, base))
 139                 return 1;
 140         while (base < bound) {
 141                 clear(tag, base);
 142                 base += 4;
 143         }
 144         return 0;
 145 }
 146
 147 static int
 148 busy_object(uint8_t *tag, void *addr) {
 149         int     base;
 150
 151         if (!addr)
 152                 return 1;
 153
 154         if ((uint8_t *) addr < ao_lisp_pool || ao_lisp_pool + AO_LISP_POOL <= (uint8_t*) addr)
 155                 return 1;
 156
 157         base = (uint8_t *) addr - ao_lisp_pool;
 158         base = limit(base);
 159         if (busy(tag, base))
 160                 return 1;
 161         return 0;
 162 }
 163
 164 static void     *move_old, *move_new;
 165 static int      move_size;
 166
 167 static void
 168 move_object(void)
 169 {
 170         int     i;
 171
 172         DBG_RESET();
 173         DBG_MOVE("move %d -> %d\n", DBG_OFFSET(move_old), DBG_OFFSET(move_new));
 174         DBG_MOVE_IN();
 175         memset(ao_lisp_moving, '\0', sizeof (ao_lisp_moving));
 176         for (i = 0; i < AO_LISP_ROOT; i++) {
 177                 if (!ao_lisp_root[i].addr)
 178                         continue;
 179                 if (ao_lisp_root[i].type) {
 180                         DBG_DO(void *addr = *ao_lisp_root[i].addr);
 181                         DBG_MOVE("root %d\n", DBG_OFFSET(addr));
 182                         if (!ao_lisp_move(ao_lisp_root[i].type,
 183                                           ao_lisp_root[i].addr)) {
 184                                 DBG_MOVE("root moves from %p to %p\n",
 185                                          addr,
 186                                          *ao_lisp_root[i].addr);
 187                         }
 188                 } else {
 189                         DBG_DO(ao_poly p = *(ao_poly *) ao_lisp_root[i].addr);
 190                         if (!ao_lisp_poly_move((ao_poly *) ao_lisp_root[i].addr)) {
 191                                 DBG_MOVE("root poly move from %04x to %04x\n",
 192                                          p, *(ao_poly *) ao_lisp_root[i].addr);
 193                         }
 194                 }
 195         }
 196         DBG_MOVE_OUT();
 197         DBG_MOVE("move done\n");
 198 }
 199
 200 #if DBG_DUMP
 201 static void
 202 dump_busy(void)
 203 {
 204         int     i;
 205         printf("busy:");
 206         for (i = 0; i < ao_lisp_top; i += 4) {
 207                 if ((i & 0xff) == 0)
 208                         printf("\n");
 209                 else if ((i & 0x1f) == 0)
 210                         printf(" ");
 211                 if (busy(ao_lisp_busy, i))
 212                         putchar('*');
 213                 else
 214                         putchar('-');
 215         }
 216         printf ("\n");
 217 }
 218 #define DUMP_BUSY()     dump_busy()
 219 #else
 220 #define DUMP_BUSY()
 221 #endif
 222
 223 static void
 224 ao_lisp_mark_busy(void)
 225 {
 226         int i;
 227
 228         memset(ao_lisp_busy, '\0', sizeof (ao_lisp_busy));
 229         DBG("mark\n");
 230         for (i = 0; i < AO_LISP_ROOT; i++) {
 231                 if (ao_lisp_root[i].type) {
 232                         void **a = ao_lisp_root[i].addr, *v;
 233                         if (a && (v = *a)) {
 234                                 DBG("root %p\n", v);
 235                                 ao_lisp_mark(ao_lisp_root[i].type, v);
 236                         }
 237                 } else {
 238                         ao_poly *a = (ao_poly *) ao_lisp_root[i].addr, p;
 239                         if (a && (p = *a)) {
 240                                 DBG("root %04x\n", p);
 241                                 ao_lisp_poly_mark(p);
 242                         }
 243                 }
 244         }
 245 }
 246
 247 void
 248 ao_lisp_collect(void)
 249 {
 250         int     i;
 251         int     top;
 252
 253         DBG("collect\n");
 254         /* Mark */
 255         ao_lisp_mark_busy();
 256
 257         DUMP_BUSY();
 258         /* Compact */
 259         DBG("find first busy\n");
 260         for (i = 0; i < ao_lisp_top; i += 4) {
 261                 if (!busy(ao_lisp_busy, i))
 262                         break;
 263         }
 264         top = i;
 265         while(i < ao_lisp_top) {
 266                 if (busy(ao_lisp_busy, i)) {
 267                         DBG("busy %d -> %d\n", i, top);
 268                         move_old = &ao_lisp_pool[i];
 269                         move_new = &ao_lisp_pool[top];
 270                         move_size = 0;
 271                         move_object();
 272                         DBG("\tbusy size %d\n", move_size);
 273                         if (move_size == 0)
 274                                 abort();
 275                         clear_object(ao_lisp_busy, move_old, move_size);
 276                         mark_object(ao_lisp_busy, move_new, move_size);
 277                         i += move_size;
 278                         top += move_size;
 279                         DUMP_BUSY();
 280                 } else {
 281                         i += 4;
 282                 }
 283         }
 284         ao_lisp_top = top;
 285 }
 286
 287
 288 int
 289 ao_lisp_mark(const struct ao_lisp_type *type, void *addr)
 290 {
 291         if (!addr)
 292                 return 1;
 293         if (mark_object(ao_lisp_busy, addr, type->size(addr)))
 294                 return 1;
 295         type->mark(addr);
 296         return 0;
 297 }
 298
 299 int
 300 ao_lisp_mark_memory(void *addr, int size)
 301 {
 302         return mark_object(ao_lisp_busy, addr, size);
 303 }
 304
 305 /*
 306  * After the object has been moved, we have to reference it
 307  * in the new location. This is only relevant for ao_lisp_poly_move
 308  * as it needs to fetch the type byte from the object, which
 309  * may have been overwritten by the copy
 310  */
 311 void *
 312 ao_lisp_move_map(void *addr)
 313 {
 314         if (addr == move_old) {
 315                 if (busy_object(ao_lisp_moving, addr))
 316                         return move_new;
 317         }
 318         return addr;
 319 }
 320
 321 static void *
 322 check_move(void *addr, int size)
 323 {
 324         if (addr == move_old) {
 325                 DBG_MOVE("mapping %d -> %d\n", DBG_OFFSET(addr), DBG_OFFSET(move_new));
 326                 if (!busy_object(ao_lisp_moving, addr)) {
 327                         DBG_MOVE("  copy %d\n", size);
 328                         memmove(move_new, move_old, size);
 329                         move_size = (size + 3) & ~3;
 330                 }
 331                 addr = move_new;
 332         }
 333         return addr;
 334 }
 335
 336 int
 337 ao_lisp_move(const struct ao_lisp_type *type, void **ref)
 338 {
 339         void            *addr = *ref;
 340         uint8_t         *a = addr;
 341         int             size = type->size(addr);
 342
 343         if (!addr)
 344                 return 1;
 345
 346 #ifndef AO_LISP_MAKE_CONST
 347         if (AO_LISP_IS_CONST(addr))
 348                 return 1;
 349 #endif
 350         DBG_MOVE("object %d\n", DBG_OFFSET(addr));
 351         if (a < ao_lisp_pool || ao_lisp_pool + AO_LISP_POOL <= a)
 352                 abort();
 353         DBG_MOVE_IN();
 354         addr = check_move(addr, size);
 355         if (addr != *ref)
 356                 *ref = addr;
 357         if (mark_object(ao_lisp_moving, addr, size)) {
 358                 DBG_MOVE("already moved\n");
 359                 DBG_MOVE_OUT();
 360                 return 1;
 361         }
 362         DBG_MOVE_OUT();
 363         DBG_MOVE("recursing...\n");
 364         DBG_MOVE_IN();
 365         type->move(addr);
 366         DBG_MOVE_OUT();
 367         DBG_MOVE("done %d\n", DBG_OFFSET(addr));
 368         return 0;
 369 }
 370
 371 int
 372 ao_lisp_move_memory(void **ref, int size)
 373 {
 374         void *addr = *ref;
 375         if (!addr)
 376                 return 1;
 377
 378         DBG_MOVE("memory %d\n", DBG_OFFSET(addr));
 379         DBG_MOVE_IN();
 380         addr = check_move(addr, size);
 381         if (addr != *ref)
 382                 *ref = addr;
 383         if (mark_object(ao_lisp_moving, addr, size)) {
 384                 DBG_MOVE("already moved\n");
 385                 DBG_MOVE_OUT();
 386                 return 1;
 387         }
 388         DBG_MOVE_OUT();
 389         return 0;
 390 }
 391
 392 #ifdef DBG_POOL
 393 static int AO_LISP_POOL_CUR = AO_LISP_POOL / 8;
 394
 395 static void
 396 ao_lisp_poison(void)
 397 {
 398         int     i;
 399
 400         printf("poison\n");
 401         ao_lisp_mark_busy();
 402         for (i = 0; i < AO_LISP_POOL_CUR; i += 4) {
 403                 uint32_t        *a = (uint32_t *) &ao_lisp_pool[i];
 404                 if (!busy_object(ao_lisp_busy, a))
 405                         *a = 0xBEEFBEEF;
 406         }
 407         for (i = 0; i < AO_LISP_POOL_CUR; i += 2) {
 408                 ao_poly         *a = (uint16_t *) &ao_lisp_pool[i];
 409                 ao_poly         p = *a;
 410
 411                 if (!ao_lisp_is_const(p)) {
 412                         void    *r = ao_lisp_ref(p);
 413
 414                         if (ao_lisp_pool <= (uint8_t *) r &&
 415                             (uint8_t *) r <= ao_lisp_pool + AO_LISP_POOL_CUR)
 416                         {
 417                                 if (!busy_object(ao_lisp_busy, r)) {
 418                                         printf("missing reference from %d to %d\n",
 419                                                (int) ((uint8_t *) a - ao_lisp_pool),
 420                                                (int) ((uint8_t *) r - ao_lisp_pool));
 421                                 }
 422                         }
 423                 }
 424         }
 425 }
 426
 427 #else
 428 #define AO_LISP_POOL_CUR AO_LISP_POOL
 429 #endif
 430
 431 void *
 432 ao_lisp_alloc(int size)
 433 {
 434         void    *addr;
 435
 436         size = ao_lisp_mem_round(size);
 437 #ifdef DBG_COLLECT_ALWAYS
 438         ao_lisp_collect();
 439 #endif
 440         if (ao_lisp_top + size > AO_LISP_POOL_CUR) {
 441 #ifdef DBG_POOL
 442                 if (AO_LISP_POOL_CUR < AO_LISP_POOL) {
 443                         AO_LISP_POOL_CUR += AO_LISP_POOL / 8;
 444                         ao_lisp_poison();
 445                 } else
 446 #endif
 447                 ao_lisp_collect();
 448 #ifdef DBG_POOL
 449                 {
 450                         int     i;
 451
 452                         for (i = ao_lisp_top; i < AO_LISP_POOL; i += 4) {
 453                                 uint32_t        *p = (uint32_t *) &ao_lisp_pool[i];
 454                                 *p = 0xbeefbeef;
 455                         }
 456                 }
 457 #endif
 458
 459                 if (ao_lisp_top + size > AO_LISP_POOL) {
 460                         ao_lisp_exception |= AO_LISP_OOM;
 461                         return NULL;
 462                 }
 463         }
 464         addr = ao_lisp_pool + ao_lisp_top;
 465         ao_lisp_top += size;
 466         return addr;
 467 }
 468
 469 int
 470 ao_lisp_root_add(const struct ao_lisp_type *type, void *addr)
 471 {
 472         int     i;
 473         DBG("add root type %p addr %p\n", type, addr);
 474         for (i = 0; i < AO_LISP_ROOT; i++) {
 475                 if (!ao_lisp_root[i].addr) {
 476                         ao_lisp_root[i].addr = addr;
 477                         ao_lisp_root[i].type = type;
 478                         return 1;
 479                 }
 480         }
 481         abort();
 482         return 0;
 483 }
 484
 485 int
 486 ao_lisp_root_poly_add(ao_poly *p)
 487 {
 488         return ao_lisp_root_add(NULL, p);
 489 }
 490
 491 void
 492 ao_lisp_root_clear(void *addr)
 493 {
 494         int     i;
 495         for (i = 0; i < AO_LISP_ROOT; i++) {
 496                 if (ao_lisp_root[i].addr == addr) {
 497                         ao_lisp_root[i].addr = 0;
 498                         ao_lisp_root[i].type = 0;
 499                         break;
 500                 }
 501         }
 502 }