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_DUMP
  32 #define DBG_OFFSET(a)   ((int) ((uint8_t *) (a) - ao_lisp_pool))
  33 #define DBG(...) printf(__VA_ARGS__)
  34 static int move_dump;
  35 static int move_depth;
  36 #define DBG_RESET() (move_depth = 0)
  37 #define DBG_MOVE(...) do { if(move_dump) { int d; for (d = 0; d < move_depth; d++) printf ("  "); printf(__VA_ARGS__); } } while (0)
  38 #define DBG_MOVE_IN()   (move_depth++)
  39 #define DBG_MOVE_OUT()  (move_depth--)
  40 #else
  41 #define DBG(...)
  42 #define DBG_RESET()
  43 #define DBG_MOVE(...)
  44 #define DBG_MOVE_IN()
  45 #define DBG_MOVE_OUT()
  46 #endif
  47
  48 uint8_t ao_lisp_exception;
  49
  50 struct ao_lisp_root {
  51         void                            **addr;
  52         const struct ao_lisp_type       *type;
  53 };
  54
  55 #define AO_LISP_ROOT    16
  56
  57 static struct ao_lisp_root      ao_lisp_root[AO_LISP_ROOT];
  58
  59 static uint8_t  ao_lisp_busy[AO_LISP_POOL / 32];
  60
  61 static uint8_t  ao_lisp_moving[AO_LISP_POOL / 32];
  62
  63 uint16_t        ao_lisp_top;
  64
  65 static inline void mark(uint8_t *tag, int offset) {
  66         int     byte = offset >> 5;
  67         int     bit = (offset >> 2) & 7;
  68         tag[byte] |= (1 << bit);
  69 }
  70
  71 static inline void clear(uint8_t *tag, int offset) {
  72         int     byte = offset >> 5;
  73         int     bit = (offset >> 2) & 7;
  74         tag[byte] &= ~(1 << bit);
  75 }
  76
  77 static inline int busy(uint8_t *tag, int offset) {
  78         int     byte = offset >> 5;
  79         int     bit = (offset >> 2) & 7;
  80         return (tag[byte] >> bit) & 1;
  81 }
  82
  83 static inline int min(int a, int b) { return a < b ? a : b; }
  84 static inline int max(int a, int b) { return a > b ? a : b; }
  85
  86 static inline int limit(int offset) {
  87         return min(AO_LISP_POOL, max(offset, 0));
  88 }
  89
  90 static int
  91 mark_object(uint8_t *tag, void *addr, int size) {
  92         int     base;
  93         int     bound;
  94
  95         if (!addr)
  96                 return 1;
  97
  98         if ((uint8_t *) addr < ao_lisp_pool || ao_lisp_pool + AO_LISP_POOL <= (uint8_t*) addr)
  99                 return 1;
 100
 101         base = (uint8_t *) addr - ao_lisp_pool;
 102         bound = base + size;
 103
 104         base = limit(base);
 105         bound = limit(bound);
 106         if (busy(tag, base))
 107                 return 1;
 108         while (base < bound) {
 109                 mark(tag, base);
 110                 base += 4;
 111         }
 112         return 0;
 113 }
 114
 115 static int
 116 clear_object(uint8_t *tag, void *addr, int size) {
 117         int     base;
 118         int     bound;
 119         if (!addr)
 120                 return 1;
 121
 122         base = (uint8_t *) addr - ao_lisp_pool;
 123         bound = base + size;
 124
 125         base = limit(base);
 126         bound = limit(bound);
 127         if (!busy(tag, base))
 128                 return 1;
 129         while (base < bound) {
 130                 clear(tag, base);
 131                 base += 4;
 132         }
 133         return 0;
 134 }
 135
 136 static int
 137 busy_object(uint8_t *tag, void *addr) {
 138         int     base;
 139
 140         if (!addr)
 141                 return 1;
 142
 143         if ((uint8_t *) addr < ao_lisp_pool || ao_lisp_pool + AO_LISP_POOL <= (uint8_t*) addr)
 144                 return 1;
 145
 146         base = (uint8_t *) addr - ao_lisp_pool;
 147         base = limit(base);
 148         if (busy(tag, base))
 149                 return 1;
 150         return 0;
 151 }
 152
 153 static void     *move_old, *move_new;
 154 static int      move_size;
 155
 156 static void
 157 move_object(void)
 158 {
 159         int     i;
 160
 161         DBG_RESET();
 162         DBG_MOVE("move %d -> %d\n", DBG_OFFSET(move_old), DBG_OFFSET(move_new));
 163         DBG_MOVE_IN();
 164         memset(ao_lisp_moving, '\0', sizeof (ao_lisp_moving));
 165         for (i = 0; i < AO_LISP_ROOT; i++)
 166                 if (ao_lisp_root[i].addr && *ao_lisp_root[i].addr) {
 167                         void *new;
 168                         DBG_MOVE("root %d\n", DBG_OFFSET(*ao_lisp_root[i].addr));
 169                         new = ao_lisp_move(ao_lisp_root[i].type, *ao_lisp_root[i].addr);
 170                         if (new)
 171                                 *ao_lisp_root[i].addr = new;
 172                 }
 173         DBG_MOVE_OUT();
 174         DBG_MOVE("move done\n");
 175 }
 176
 177 #ifdef DBG_DUMP
 178 static void
 179 dump_busy(void)
 180 {
 181         int     i;
 182         printf("busy:");
 183         for (i = 0; i < ao_lisp_top; i += 4) {
 184                 if ((i & 0xff) == 0)
 185                         printf("\n");
 186                 else if ((i & 0x1f) == 0)
 187                         printf(" ");
 188                 if (busy(ao_lisp_busy, i))
 189                         putchar('*');
 190                 else
 191                         putchar('-');
 192         }
 193         printf ("\n");
 194 }
 195 #define DUMP_BUSY()     dump_busy()
 196 #else
 197 #define DUMP_BUSY()
 198 #endif
 199
 200 void
 201 ao_lisp_collect(void)
 202 {
 203         int     i;
 204         int     top;
 205
 206         /* Mark */
 207         memset(ao_lisp_busy, '\0', sizeof (ao_lisp_busy));
 208         DBG("mark\n");
 209         for (i = 0; i < AO_LISP_ROOT; i++)
 210                 if (ao_lisp_root[i].addr && *ao_lisp_root[i].addr) {
 211                         DBG("root %p\n", *ao_lisp_root[i].addr);
 212                         ao_lisp_mark(ao_lisp_root[i].type, *ao_lisp_root[i].addr);
 213                 }
 214
 215         DUMP_BUSY();
 216         /* Compact */
 217         DBG("find first busy\n");
 218         for (i = 0; i < ao_lisp_top; i += 4) {
 219                 if (!busy(ao_lisp_busy, i))
 220                         break;
 221         }
 222         top = i;
 223         while(i < ao_lisp_top) {
 224                 if (busy(ao_lisp_busy, i)) {
 225                         DBG("busy %d -> %d\n", i, top);
 226                         move_old = &ao_lisp_pool[i];
 227                         move_new = &ao_lisp_pool[top];
 228                         move_size = 0;
 229                         move_object();
 230                         DBG("\tbusy size %d\n", move_size);
 231                         if (move_size == 0)
 232                                 abort();
 233                         clear_object(ao_lisp_busy, move_old, move_size);
 234                         mark_object(ao_lisp_busy, move_new, move_size);
 235                         i += move_size;
 236                         top += move_size;
 237                         DUMP_BUSY();
 238                 } else {
 239                         i += 4;
 240                 }
 241         }
 242         ao_lisp_top = top;
 243 }
 244
 245
 246 void
 247 ao_lisp_mark(const struct ao_lisp_type *type, void *addr)
 248 {
 249         if (!addr)
 250                 return;
 251         if (mark_object(ao_lisp_busy, addr, type->size(addr)))
 252                 return;
 253         type->mark(addr);
 254 }
 255
 256 int
 257 ao_lisp_mark_memory(void *addr, int size)
 258 {
 259         return mark_object(ao_lisp_busy, addr, size);
 260 }
 261
 262 /*
 263  * After the object has been moved, we have to reference it
 264  * in the new location. This is only relevant for ao_lisp_poly_move
 265  * as it needs to fetch the type byte from the object, which
 266  * may have been overwritten by the copy
 267  */
 268 void *
 269 ao_lisp_move_map(void *addr)
 270 {
 271         if (addr == move_old) {
 272                 if (busy_object(ao_lisp_moving, addr))
 273                         return move_new;
 274         }
 275         return addr;
 276 }
 277
 278 static void *
 279 check_move(void *addr, int size)
 280 {
 281         if (addr == move_old) {
 282                 DBG_MOVE("mapping %d -> %d\n", DBG_OFFSET(addr), DBG_OFFSET(move_new));
 283                 if (!busy_object(ao_lisp_moving, addr)) {
 284                         DBG_MOVE("  copy %d\n", size);
 285                         memmove(move_new, move_old, size);
 286                         move_size = (size + 3) & ~3;
 287                 }
 288                 addr = move_new;
 289         }
 290         return addr;
 291 }
 292
 293 void *
 294 ao_lisp_move(const struct ao_lisp_type *type, void *addr)
 295 {
 296         uint8_t *a = addr;
 297         int     size = type->size(addr);
 298
 299         if (!addr)
 300                 return NULL;
 301
 302 #ifndef AO_LISP_MAKE_CONST
 303         if (AO_LISP_IS_CONST(addr))
 304                 return addr;
 305 #endif
 306         DBG_MOVE("object %d\n", DBG_OFFSET(addr));
 307         if (a < ao_lisp_pool || ao_lisp_pool + AO_LISP_POOL <= a)
 308                 abort();
 309         DBG_MOVE_IN();
 310         addr = check_move(addr, size);
 311         if (mark_object(ao_lisp_moving, addr, size)) {
 312                 DBG_MOVE("already moved\n");
 313                 DBG_MOVE_OUT();
 314                 return addr;
 315         }
 316         DBG_MOVE_OUT();
 317         DBG_MOVE("recursing...\n");
 318         DBG_MOVE_IN();
 319         type->move(addr);
 320         DBG_MOVE_OUT();
 321         DBG_MOVE("done %d\n", DBG_OFFSET(addr));
 322         return addr;
 323 }
 324
 325 void *
 326 ao_lisp_move_memory(void *addr, int size)
 327 {
 328         if (!addr)
 329                 return NULL;
 330
 331         DBG_MOVE("memory %d\n", DBG_OFFSET(addr));
 332         DBG_MOVE_IN();
 333         addr = check_move(addr, size);
 334         if (mark_object(ao_lisp_moving, addr, size)) {
 335                 DBG_MOVE("already moved\n");
 336                 DBG_MOVE_OUT();
 337                 return addr;
 338         }
 339         DBG_MOVE_OUT();
 340         return addr;
 341 }
 342
 343 void *
 344 ao_lisp_alloc(int size)
 345 {
 346         void    *addr;
 347
 348         size = ao_lisp_mem_round(size);
 349         if (ao_lisp_top + size > AO_LISP_POOL) {
 350                 ao_lisp_collect();
 351                 if (ao_lisp_top + size > AO_LISP_POOL) {
 352                         ao_lisp_exception |= AO_LISP_OOM;
 353                         return NULL;
 354                 }
 355         }
 356         addr = ao_lisp_pool + ao_lisp_top;
 357         ao_lisp_top += size;
 358         return addr;
 359 }
 360
 361 int
 362 ao_lisp_root_add(const struct ao_lisp_type *type, void *addr)
 363 {
 364         int     i;
 365         DBG("add root type %p addr %p\n", type, addr);
 366         for (i = 0; i < AO_LISP_ROOT; i++) {
 367                 if (!ao_lisp_root[i].addr) {
 368                         ao_lisp_root[i].addr = addr;
 369                         ao_lisp_root[i].type = type;
 370                         return 1;
 371                 }
 372         }
 373         abort();
 374         return 0;
 375 }
 376
 377 void
 378 ao_lisp_root_clear(void *addr)
 379 {
 380         int     i;
 381         for (i = 0; i < AO_LISP_ROOT; i++) {
 382                 if (ao_lisp_root[i].addr == addr) {
 383                         ao_lisp_root[i].addr = 0;
 384                         ao_lisp_root[i].type = 0;
 385                         break;
 386                 }
 387         }
 388 }